The extension of interactive proofs of proximity to the distribution-free setting is indeed called for, and parallels an anlogous extension that was considered in the context of property testing. In both cases, rather than treating all entries in the object as equal and considering the uniform distribution as the basis for the definition of distance, we consider an arbitrary distribution on these entries as a basis for the definition of distance. Needless to say, in such a case, the tester/verifier is provided with samples to this (a priori) unknown distribution.
I find it quite remarkable that the current work succeeds in achieving general results within this context (of distribution-free verification). Given this perspective, I view the fact that in many cases the results in this context match those known for the restricted setting of uniform distribution as an extra.
Let me seize the opportunity to state the main results of RVW13 (as improved by RR20) in a more friendly manner.
RVW13 (as improved by RR20):
For every $k\leq n$, every set in NC has an IPP
with query complexity $(k+(1/\eps))\cdot\poly(\log n)$
and communication complexity $tildeO(n)/k$.
Furthermore, The IPP has $\poly(\log n)$ rounds.
In the finer stmt, the polylog is replaced by depth times polylog(size).
(In RVW, the polylogs are replaced by $n^{o(1)}$.)
Likewise, the main result of the current work,
which refer to distribution-free IPP (hereafter denoted df-IPP),
may be stated as follows.
Thm 1.1 (restated): For every $k\leq \sqrt n$, every set in NC has an df-IPP with query and sample complexities $k+O(1/\eps)$ and communication complexity $\tildeO((n/k)+(1/\eps))$. Furthermore, The IPP has $\poly(\log n)$ rounds (and the finer stmt is as in RVW13).
NOTE (March 1st, 2024): See revision, which states better results.
Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured according to an arbitrary and unknown input distribution $\mathcal{D} \sim [n]$. As usual in property testing, the tester is required to do so while making only a sublinear number of input queries, but as the distribution is unknown, we also allow a sublinear number of samples from the distribution $\mathcal{D}$.
In this work we initiate the study of distribution-free interactive proofs of proximity (df-IPP) in which the distribution-free testing algorithm is assisted by an all powerful but untrusted prover.
Our main result is a df-$IPP$ for any problem $\Pi \in NC$, with $\tilde{O}(\sqrt{n})$ communication, sample, query, and verification complexities, for any proximity parameter $\varepsilon>1/\sqrt{n}$. For such proximity parameters, this result matches the parameters of the best-known general purpose $IPP$s in the standard uniform setting, and is optimal under reasonable cryptographic assumptions.
For general values of the proximity parameter $\varepsilon$, our distribution-free $IPP$ has optimal query complexity $O(1/\varepsilon)$ but the communication complexity is $\tilde{O}(\varepsilon \cdot n + 1/\varepsilon)$, which is worse than what is known for uniform $IPP$s when $\varepsilon<1/\sqrt{n}$. With the aim of improving on this gap, we further show that for $IPP$s over specialised, but large distribution families, such as sufficiently smooth distributions and product distributions, the communication complexity can be reduced to $\varepsilon\cdot n\cdot (1/\varepsilon)^{o(1)}$ (keeping the query complexity roughly the same as before) to match the communication complexity of the uniform case. In addition, we show that for certain natural families of languages, such as symmetric and (relaxed) self-correctable languages, i t is possible to further improve the efficiency of distribution-free $IPP$s.
See ECCC TR23-118.