Repository logo

An Exponential Separation Between MA and AM Proofs of Proximity

Published version

Repository DOI



Change log


Liu, YP 
Rothblum, RD 


jats:titleAbstract</jats:title>jats:pInteractive proofs of proximity allow a sublinear-time verifier to check that a given input is jats:italicclose</jats:italic> to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work, we consider two natural jats:italicminimally interactive</jats:italic> variants of such proofs systems, in which the prover only sends a single message, referred to as the proof. </jats:p>jats:pThe first variant, known as -proofs of Proximity (), is fully jats:italicnon-interactive</jats:italic>, meaning that the proof is a function of the input jats:italiconly</jats:italic>. The second variant, known as -proofs of Proximity (), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both s and s is the total number of bits that the verifier observes—namely, the sum of the proof length and query complexity. </jats:p>jats:pOur main result is an exponential separation between the power of s and s. Specifically, we exhibit an explicit and natural property jats:inline-formulajats:alternativesjats:tex-math$$\Pi$$</jats:tex-math><mml:math xmlns:mml=""> mml:miΠ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> that admits an with complexity jats:inline-formulajats:alternativesjats:tex-math$$O(\log n)$$</jats:tex-math><mml:math xmlns:mml=""> mml:mrow mml:miO</mml:mi> mml:mo(</mml:mo> mml:molog</mml:mo> mml:min</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, whereas any for jats:inline-formulajats:alternativesjats:tex-math$$\Pi$$</jats:tex-math><mml:math xmlns:mml=""> mml:miΠ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> has complexity jats:inline-formulajats:alternativesjats:tex-math$$\tilde{\Omega}(n^{1/4})$$</jats:tex-math><mml:math xmlns:mml=""> mml:mrow mml:mover mml:miΩ</mml:mi> mml:mo~</mml:mo> </mml:mover> mml:mrow mml:mo(</mml:mo> mml:msup mml:min</mml:mi> mml:mrow mml:mn1</mml:mn> mml:mo/</mml:mo> mml:mn4</mml:mn> </mml:mrow> </mml:msup> mml:mo)</mml:mo> </mml:mrow> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, where jats:italicn</jats:italic> denotes the length of the input in bits. Our lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (jats:italicQuantum Information</jats:italic> & jats:italicComputation</jats:italic> 2012) has shown a jats:inline-formulajats:alternativesjats:tex-math$$\Omega(n^{1/6})$$</jats:tex-math><mml:math xmlns:mml=""> mml:mrow mml:miΩ</mml:mi> mml:mo(</mml:mo> mml:msup mml:min</mml:mi> mml:mrow mml:mn1</mml:mn> mml:mo/</mml:mo> mml:mn6</mml:mn> </mml:mrow> </mml:msup> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> lower bound for the same property jats:inline-formulajats:alternativesjats:tex-math$$\Pi$$</jats:tex-math><mml:math xmlns:mml=""> mml:miΠ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>.</jats:p>jats:pLastly, we also consider the notion of jats:italicoblivious</jats:italic> proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting, we show that s can only be quadratically stronger than s. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.</jats:p>



Interative proofs, proofs of proximity

Journal Title

Computational Complexity

Conference Name

Journal ISSN


Volume Title



Springer Science and Business Media LLC
UK Research and Innovation (MR/S031545/1)