All reports by Author Itai Leigh:

__
TR23-071
| 8th May 2023
__

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov#### Sampling and Certifying Symmetric Functions

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>