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-209 | 25th September 2026 00:14

Interactive Proofs with Noisy Data

RSS-Feed




TR26-209
Authors: Noga Amit, Guy Rothblum, shafi goldwasser
Publication: 25th September 2026 16:24
Downloads: 38
Keywords: 


Abstract:

We study interactive proofs when the prover and the verifier access the same underlying data through independent noisy views. The noise is \emph{persistent} for each party: each location is corrupted once, and repeated queries to the same location return the same corrupted value. We introduce two models in this setting: \emph{noisy interactive proofs of proximity} (noisy IPPs), and \emph{noisy PAC verification}, a noisy analogue of the PAC verification framework of Goldwasser et al.\ [ITCS 2021]. These are the first interactive-proof models in which the prover and verifier access the same data through separate noisy views, possibly with different noise rates, rather than sharing a common view of the input.

For noisy IPPs, we give a complete characterization of the four natural regimes determined by whether the honest prover is clean or noisy and whether the exact noise rates are known or only upper bounds are known. We show that the clean-prover, known-rate setting admits noisy IPPs for every language in $NC$, whereas, under a standard cryptographic assumption, in each of the other three regimes there is a language in $NC^1$ for which noisy IPPs are impossible. The positive result is obtained through a connection to \emph{robust} IPPs: even subconstant robustness suffices to tolerate constant random noise. We also show that constant robustness is impossible in general, establishing a separation between random noise and worst-case local corruptions.

Beyond these general results, we construct noisy IPPs for natural languages, and we give a noisy PAC-verification protocol for the heavy Fourier coefficients of a Boolean function. These positive results are efficient for both the verifier and the prover, and hold in the general setting where the parties know only an upper bound on the noise rate and may experience different noise rates.



ISSN 1433-8092 | Imprint