2026-07-23T19:43:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8153 2024-03-06T10:39:20Z ddc:004 open_access

A Hierarchy Theorem for Interactive Proofs of Proximity Gur, Tom Rothblum, Ron D. Complexity Theory Property Testing Interactive Proofs The number of rounds, or round complexity, used in an interactive protocol is a fundamental resource. In this work we consider the significance of round complexity in the context of Interactive Proofs of Proximity (IPPs). Roughly speaking, IPPs are interactive proofs in which the verifier runs in sublinear time and is only required to reject inputs that are far from the language. Our main result is a round hierarchy theorem for IPPs, showing that the power of IPPs grows with the number of rounds. More specifically, we show that there exists a gap function g(r) = Theta(r^2) such that for every constant r \geq 1 there exists a language that (1) has a g(r)-round IPP with verification time t=t(n,r) but (2) does not have an r-round IPP with verification time t (or even verification time t'=\poly(t)). In fact, we prove a stronger result by exhibiting a single language L such that, for every constant r \geq 1, there is an O(r^2)-round IPP for L with t=n^{O(1/r)} verification time, whereas the verifier in any r-round IPP for L must run in time at least t^{100}. Moreover, we show an IPP for L with a poly-logarithmic number of rounds and only poly-logarithmic erification time, yielding a sub-exponential separation between the power of constant-round IPPs versus general (unbounded round) IPPs. From our hierarchy theorem we also derive implications to standard interactive proofs (in which the verifier can run in polynomial time). Specifically, we show that the round reduction technique of Babai and Moran (JCSS, 1988) is (almost) optimal among all blackbox transformations, and we show a connection to the algebrization framework of Aaronson and Wigderson (TOCT, 2009). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tom Gur and Ron D. Rothblum 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.39 urn:nbn:de:0030-drops-81536 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.39 eng https://creativecommons.org/licenses/by/3.0/legalcode