Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-088 | 29th May 2026 15:12

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

RSS-Feed




TR26-088
Authors: Oded Goldreich
Publication: 29th May 2026 15:13
Downloads: 115
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