Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INTERACTIVE PROOF SYSTEMS:
Reports tagged with Interactive proof systems:
TR17-018 | 6th February 2017
Oded Goldreich, Guy Rothblum

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

Revisions: 3


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




ISSN 1433-8092 | Imprint