Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-201 | 4th December 2025 10:01

Interactive proof systems for FARNESS

RSS-Feed

Abstract:

We consider interactive proofs for the promise problem, called $\epsilon$-FARNESS, in which the yes-instances are pairs of distributions over $[n]$ that are $\epsilon$-far from one another, and the no-instances are pairs of identical distributions.
For any $t\leq n^{2/3}$, we obtain an interactive proof in which the verifier has sample complexity $O(t/\epsilon^2)$ and the (honest) prover has sample complexity $\poly(1/\epsilon)\cdot(n/{\sqrt t})$.
For $t=n^{2/3}$ this result is the best possible, because (as proved by Batu and Canonne (FOCS 2017)) the corresponding decision procedure has sample complexity $\Omega(n^{2/3})$.

We also obtain interactive proofs for the promise problem in which the yes-instances are distributions over $[n]$ that are $\epsilon$-far from the uniform distribution, and the no-instance is the uniform distribution.
For any $t\leq{\sqrt n}$, we obtain an interactive proof in which the verifier has sample complexity $O(t/\epsilon^2)$ and the (honest) prover has sample complexity $\poly(1/\epsilon)\cdot\tildeO(n/t)$.
This stand in contrast to the fact (proved by Chiesa and Gur (ITCS 2018)) that the verifier in any interactive proof for the complement promise problem must have sample complexity $\Omega({\sqrt n})$.



ISSN 1433-8092 | Imprint