DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.72

Public Coin Interactive Proofs for Label-Invariant Distribution Properties

Authors: Tal Herman

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

Assume we are given sample access to an unknown distribution D over a large domain [N]. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, can be efficiently and verifiably approximated through interaction with an untrusted powerful prover, that knows the entire distribution [Herman and Rothblum, STOC 2022, FOCS 2023]. Concretely, these works provide an efficient proof system for approximation of any label-invariant distribution quantity (i.e. any function over the distribution that’s invariant to a re-labeling of the domain [N]). In our main result, we present the first efficient public coin AM protocol, for any label-invariant property. Our protocol achieves sample complexity and communication complexity of magnitude Õ(N^{2/3}), while the proof can be generated in quasi-linear Õ(N) time. On top of that, we also give a public-coin protocol for efficiently verifying the distance a between a samplable distribution D, and some explicitly given distribution Q.

Cite as

Tal Herman. Public Coin Interactive Proofs for Label-Invariant Distribution Properties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 72:1-72:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{herman:LIPIcs.APPROX/RANDOM.2024.72,
  author =	{Herman, Tal},
  title =	{{Public Coin Interactive Proofs for Label-Invariant Distribution Properties}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{72:1--72:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.72},
  URN =		{urn:nbn:de:0030-drops-210654},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.72},
  annote =	{Keywords: Interactive Proof Systems, Distribution Testing, Public-Coin Protocols}
}

Search Results

Documents authored by Herman, Tal

Public Coin Interactive Proofs for Label-Invariant Distribution Properties

Abstract

Cite as

Thanks for your feedback!

Could not send message