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

#### Webpage for a paper by Oded Goldreich and Guy Rothblum

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

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.