Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with interactive proof system:
TR95-013 | 24th February 1995
Oleg Verbitsky

The Parallel Repetition Conjecture for Trees is True

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the
error probability of a two prover one round interactive protocol repeated $n$
times in parallel is exponentially small in $n$.
We show that the PRC is true in the case when
the bipartite graph of dependence between ... more >>>

TR18-069 | 14th April 2018
Oded Goldreich, Guy Rothblum

Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more ... more >>>

TR22-124 | 9th September 2022
Oded Goldreich, Guy Rothblum, Tal Skverer

On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 2

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make ... more >>>

ISSN 1433-8092 | Imprint