All reports by Author Hugo Aaronson:

__
TR23-118
| 17th August 2023
__

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum#### Distribution-Free Proofs of Proximity

Revisions: 2

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum

Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured ... more >>>