Auditing Local Explanations is Hard

Neural Information Processing Systems 

We prove upper and lower bounds on the amount of queries that are needed for an auditor to succeed within this framework.