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

Webpage for a paper by Oded Goldreich


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 $\NC$ (and beyond). We also present limitations on the power of constant-round IPP systems.

Material available on-line


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