Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ITAI LEIGH:
All reports by Author Itai Leigh:

TR23-071 | 8th May 2023
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Sampling and Certifying Symmetric Functions

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 >>>




ISSN 1433-8092 | Imprint