TR26-088 | A digest of the work of Rothblum, Vadhan, and Wigderson (2013) | Oded Goldreich

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.