Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-018 | 3rd March 2017 10:56

Simple doubly-efficient interactive proof systems for locally-characterizable sets

RSS-Feed




Revision #2
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 3rd March 2017 10:56
Downloads: 118
Keywords: 


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 $\cal 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)



Changes to previous version:

Correcting a typo that made a minor unfavorable comparison (against our own construction).


Revision #1 to TR17-018 | 2nd March 2017 20:01

Simple doubly-efficient interactive proof systems for locally-characterizable sets





Revision #1
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 2nd March 2017 20:01
Downloads: 76
Keywords: 


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 $\cal 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)



Changes to previous version:

Added a few references we were not aware of, and a comment asserting that the proof system underlying Thm 1 applies also to verifying the number of violated conditions.


Paper:

TR17-018 | 6th February 2017 16:44

Simple doubly-efficient interactive proof systems for locally-characterizable sets





TR17-018
Authors: Oded Goldreich, Guy Rothblum
Publication: 6th February 2017 16:44
Downloads: 211
Keywords: 


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 $\cal 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)



ISSN 1433-8092 | Imprint