All reports by Author Tal Herman:

__
TR24-141
| 12th September 2024
__

Tal Herman#### Public Coin Interactive Proofs for Label-Invariant Distribution Properties

__
TR24-094
| 19th May 2024
__

Tal Herman, Guy Rothblum#### Interactive Proofs for General Distribution Properties

__
TR23-161
| 1st November 2023
__

Tal Herman, Guy Rothblum#### Doubly-Efficient Interactive Proofs for Distribution Properties

Revisions: 1

__
TR22-052
| 18th April 2022
__

Tal Herman, Guy Rothblum#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

Tal Herman

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, ... more >>>

Tal Herman, Guy Rothblum

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using ... more >>>

Tal Herman, Guy Rothblum

Suppose we have access to a small number of samples from an unknown distribution, and would like learn facts about the distribution.

An untrusted data server claims to have studied the distribution and makes assertions about its properties. Can the untrusted data server prove that its assertions are approximately correct? ...
more >>>

Tal Herman, Guy Rothblum

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>