Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR23-118 | 16th February 2024 18:18

Distribution-Free Proofs of Proximity

RSS-Feed




Revision #2
Authors: Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum
Accepted on: 16th February 2024 18:18
Downloads: 9
Keywords: 


Abstract:

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$s) in which the distribution-free testing algorithm is assisted by an all powerful but untrusted prover. Our main result is that for any problem $\Pi \in NC$, any proximity parameter $\varepsilon > 0$, and any (trade-off) parameter $\tau\leq\sqrt{n}$, we construct a df-$IPP$ for $\Pi$ with respect to $\varepsilon$, that has query and sample complexities $\tau+O(1/\varepsilon)$, and communication complexity $\tilde{O}(n/\tau + 1/\varepsilon)$. For $\tau$ as above and sufficiently large $\varepsilon$ (namely, when $\varepsilon > \tau/n$), this result matches the parameters of the best-known general purpose $IPP$s in the standard uniform setting. Moreover, for such $\tau$, its parameters are optimal up to poly-logarithmic factors under reasonable cryptographic assumptions for the same regime of $\varepsilon$ as the uniform setting, i.e., when $\varepsilon \geq 1/\tau$.

For smaller values of $\varepsilon$ (i.e., when $\varepsilon< \tau/n$), our protocol has communication complexity $\Omega(1/\varepsilon)$, which is worse than the $\tilde{O}(n/\tau)$ communication complexity of the uniform $IPP$s (with the same query complexity). 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 $\tilde{O}(n/\tau^{1-o(1)})$. In addition, we show that for certain natural families of languages, such as symmetric and (relaxed) self-correctable languages, it is possible to further improve the efficiency of distribution-free $IPP$s.



Changes to previous version:

Fixed Latex and changed the parameterisation of the main results.


Revision #1 to TR23-118 | 16th February 2024 17:30

Distribution-Free Proofs of Proximity





Revision #1
Authors: Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum
Accepted on: 16th February 2024 17:30
Downloads: 3
Keywords: 


Abstract:

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 $\sD \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 $\sD$.

In this work we initiate the study of distribution-free interactive proofs of proximity (df-$\IPP$s) in which the distribution-free testing algorithm is assisted by an all powerful but untrusted prover. Our main result is that for any problem $\Pi \in \NC$, any proximity parameter $\eps > 0$, and any (trade-off) parameter $\tau\leq\sqrt{n}$, we construct a df-$\IPP$ for $\Pi$ with respect to $\eps$, that has query and sample complexities $\tau+O(1/\eps)$, and communication complexity $\Tilde{O}(n/\tau + 1/\eps)$. For $\tau$ as above and sufficiently large $\eps$ (namely, when $\eps > \tau/n$), this result matches the parameters of the best-known general purpose $\IPP$s in the standard uniform setting. Moreover, for such $\tau$, its parameters are optimal up to poly-logarithmic factors under reasonable cryptographic assumptions for the same regime of $\eps$ as the uniform setting, i.e., when $\eps \geq 1/\tau$.

For smaller values of $\eps$ (i.e., when $\eps < \tau/n$), our protocol has communication complexity $\Omega(1/\eps)$, which is worse than the $\Tilde{O}(n/\tau)$ communication complexity of the uniform $\IPP$s (with the same query complexity). 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 $\Tilde{O}(n/\tau^{1-o(1)})$. In addition, we show that for certain natural families of languages, such as symmetric and (relaxed) self-correctable languages, it is possible to further improve the efficiency of distribution-free $\IPP$s.


Paper:

TR23-118 | 17th August 2023 11:43

Distribution-Free Proofs of Proximity





TR23-118
Authors: Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum
Publication: 17th August 2023 12:45
Downloads: 229
Keywords: 


Abstract:

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 \emph{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, it is possible to further improve the efficiency of distribution-free $IPP$s.



ISSN 1433-8092 | Imprint