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 TR26-088 | 18th June 2026 15:21

A digest of the work of Rothblum, Vadhan, and Wigderson (2013)

RSS-Feed




Revision #2
Authors: Oded Goldreich
Accepted on: 18th June 2026 15:21
Downloads: 1
Keywords: 


Abstract:

The work of Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013) is pivotal to the study of interactive proofs of proximity (IPPs).
We present the main contents of their work, while clarify a few (conceptual) aspects.
Specifically, starting with the definition of IPP systems, our main focus is on the construction of IPP systems for any property in log-space uniform $\cal NC$ (and beyond).
We also present limitations on the power of constant-round IPP systems.



Changes to previous version:

Omitting the condition $\mu'\leq1/|F|$ from Lemma 2.3,
adding a new FN14 on $P_{\F,d}$ and a new FN20 on private to public coin.


Revision #1 to TR26-088 | 31st May 2026 10:17

A digest of the work of Rothblum, Vadhan, and Wigderson (2013)





Revision #1
Authors: Oded Goldreich
Accepted on: 31st May 2026 10:17
Downloads: 93
Keywords: 


Abstract:

The work of Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013) is pivotal to the study of interactive proofs of proximity (IPPs).
We present the main contents of their work, while clarify a few (conceptual) aspects.
Specifically, starting with the definition of IPP systems, our main focus is on the construction of IPP systems for any property in log-space uniform $\cal NC$ (and beyond).
We also present limitations on the power of constant-round IPP systems.



Changes to previous version:

Slightly rephrasing Theorem 2 and Lemma 2.1.
Clarifying Footnote 11.
Correcting a few typos.


Paper:

TR26-088 | 29th May 2026 15:12

A digest of the work of Rothblum, Vadhan, and Wigderson (2013)





TR26-088
Authors: Oded Goldreich
Publication: 29th May 2026 15:13
Downloads: 275
Keywords: 


Abstract:

The work of Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013) is pivotal to the study of interactive proofs of proximity (IPPs).
We present the main contents of their work, while clarify a few (conceptual) aspects.
Specifically, starting with the definition of IPP systems, our main focus is on the construction of IPP systems for any property in log-space uniform $\cal NC$ (and beyond).
We also present limitations on the power of constant-round IPP systems.



ISSN 1433-8092 | Imprint