Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

A hierarchy theorem for interactive proofs of proximity

Tools
- Tools
+ Tools

Gur, Tom and Rothblum, Ron D. (2017) A hierarchy theorem for interactive proofs of proximity. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Published in: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 67 39:1-39:43. ISBN 9783959770293. doi:10.4230/LIPIcs.ITCS.2017.39 ISSN 1868-8969.

[img]
Preview
PDF
WRAP-hierarchy-therorem-interactive-proofs-proximity-Gur-2017.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (1007Kb) | Preview
Official URL: http://drops.dagstuhl.de/opus/volltexte/2017/8153

Request Changes to record.

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 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).

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Computational complexity
Series Name: Leibniz International Proceedings in Informatics (LIPIcs)
Journal or Publication Title: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of Publication: Dagstuhl, Germany
ISBN: 9783959770293
ISSN: 1868-8969
Official Date: 2017
Dates:
DateEvent
2017Published
30 October 2016Accepted
Volume: 67
Page Range: 39:1-39:43
DOI: 10.4230/LIPIcs.ITCS.2017.39
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access (Creative Commons)
Date of first compliant deposit: 11 April 2019
Date of first compliant Open Access: 11 April 2019
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
671/13Israel Science Foundationhttp://dx.doi.org/10.13039/501100003977
239985European Research Councilhttp://viaf.org/viaf/130022607
MACS-CNS-1413920National Science Foundationhttp://dx.doi.org/10.13039/100000001
UNSPECIFIEDSimons Foundationhttp://dx.doi.org/10.13039/100000893
Conference Paper Type: Paper
Title of Event: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Type of Event: Conference

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us