Spoofing Generalization: When Can't You Trust Proprietary Models?

On the computational complexity of algorithms

Juris Hartmanis and Richard E Stearns · 1965

Earlier work this paper cites.

Universal classes of hash functions

J Lawrence Carter and Mark N Wegman · 1979

Earlier work this paper cites.

The complexity of computing the permanent

Original

Leslie G Valiant · 1979

Earlier work this paper cites.

Unique signatures and verifiable random functions from the dh-ddh separation

Anna Lysyanskaya · 2002

Earlier work this paper cites.

Derandomizing polynomial identity tests means proving circuit lower bounds

Valentine Kabanets and Russell Impagliazzo · 2004

Earlier work this paper cites.

Uniform direct product theorems: simplified, optimized, and derandomized

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson · 2010

Cited alongside, same era.

On the (im) possibility of obfuscating programs

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang · 2012

Cited alongside, same era.

Spectrally-normalized margin bounds for neural networks

Original

Peter Bartlett, Dylan J Foster, and Matus Telgarsky · 2017

Cited alongside, same era.

Size-independent sample complexity of neural networks

Noah Golowich, Alexander Rakhlin, and Ohad Shamir · 2018

Cited alongside, same era.

The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery

Zachary C Lipton · 2018

Later among the works it cites.

Quantifying interpretability and trust in machine learning systems

Original

Philipp Schmidt and Felix Biessmann · 2019

Later among the works it cites.

Robustness in machine learning explanations: does it matter?

Leif Hancox-Li · 2020

Later among the works it cites.

Indistinguishability obfuscation from well-founded assumptions

Original

Aayush Jain, Huijia Lin, and Amit Sahai · 2021

Closest in time.