In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 ...
more >>>
Interactive proofs of proximity for distributions, introduced by Chiesa and Gur (ITCS18) and extensively studied recently by Herman and Rothblum (STOC22, FOCS23, FOCS24}, offer a way of verifying properties of distributions using less samples than required to test these properties.
We say that such an interactive proof system is {\sf ... more >>>
We revisit the setting of Interactive Proof Systems for Distribution Testing, introduced by Chiesa and Gur (2018), showing that a simple twist on the task requirements may lead to dramatic improvements, allowing verifiers with constant sample complexity.
We define and investigate the multi-prover and zero-knowledge versions of these interactive proof ... more >>>
