## On the doubly-efficient interactive proof systems of GKR

#### Webpage for an exposition by Oded Goldreich

#### Abstract

We present a somewhat simpler variant
of the doubly-efficient interactive proof systems
of Goldwasser, Kalai, and Rothblum (JACM, 2015).
Recall that these proof systems apply to log-space uniform sets in NC
(or, more generally, to inputs that are acceptable by log-space
uniform bounded-depth circuits, where the number of rounds in the
proof system is linearly related to the depth of the circuit).
Our simplification is in the handling of the log-space uniformity condition.
Rather than having the prover provide the verifier with bits
of the encoding of the circuit and establish their correctness,
we employ the proof system to a highly regular universal circuit
that constructs and evaluates the log-space uniform circuit in question.

#### Material available on-line

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