LIPIcs.ITCS.2018.18.pdf
- Filesize: 0.63 MB
- 19 pages
Document
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
Authors
-
Part of:
Volume:
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-01-12
Cite As Get BibTex
Oded Goldreich and Guy N. Rothblum. Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.18
Abstract
A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time. We present direct constructions of doubly-efficient interactive proof systems for problems in P that are believed to have relatively high complexity. Specifically, such constructions are presented for t-CLIQUE and t-SUM. In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC). The proof systems presented by us are significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016), and can be implemented using a smaller number of rounds.
Subject Classification
Keywords
- Interactive proofs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads