All reports by Author Marcel Dall'Agnol:

__
TR21-068
| 8th May 2021
__

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler#### Quantum Proofs of Proximity

__
TR20-154
| 10th October 2020
__

Marcel Dall'Agnol, Tom Gur, Oded Lachish#### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>