Gur, Tom ;
Rothblum, Ron D.
A Hierarchy Theorem for Interactive Proofs of Proximity
Abstract
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 rround 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 rround IPP for L must run in time at least t^{100}. Moreover, we show an IPP for L with a polylogarithmic number of rounds and only polylogarithmic erification time, yielding a subexponential separation between the power of constantround 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).
BibTeX  Entry
@InProceedings{gur_et_al:LIPIcs:2017:8153,
author = {Tom Gur and Ron D. Rothblum},
title = {{A Hierarchy Theorem for Interactive Proofs of Proximity}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {39:139:43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8153},
URN = {urn:nbn:de:0030drops81536},
doi = {10.4230/LIPIcs.ITCS.2017.39},
annote = {Keywords: Complexity Theory, Property Testing, Interactive Proofs}
}
28.11.2017
Keywords: 

Complexity Theory, Property Testing, Interactive Proofs 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

28.11.2017 