ECCC-Report TR23-071https://eccc.weizmann.ac.il/report/2023/071Comments and Revisions published for TR23-071en-usSun, 14 May 2023 14:04:25 +0300
Paper TR23-071
| Sampling and Certifying Symmetric Functions |
Artur Riazanov,
Yuval Filmus,
Dmitry Sokolov,
Itai Leigh
https://eccc.weizmann.ac.il/report/2023/071A 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$ for decision forests, i.e. every output bit is computed as a decision tree of the inputs. For every $k$ there is an $O(\log n)$-depth decision forest sampling $\mathbf{U}^n_k$ with an inverse-polynomial error [Viola 2012, Czumaj 2015]. We show that for every $\epsilon > 0$ there exists $\tau$ such that for decision depth $\tau \log (n/k) / \log \log (n/k)$, the error for sampling $\mathbf{U}_k^n$ is at least $1-\epsilon$. Our result is based on the recent robust sunflower lemma [Alweiss, Lovett, Wu, Zhang 2021, Rao 2019].
Our second result is about matching a set of $n$-bit strings with the image of a $d$-local circuit, i.e. such that each output bit depends on at most $d$ input bits. We study the set of all $n$-bit strings whose Hamming weight is at least $n/2$. We improve the previously known locality lower bound from $\Omega(\log^* n)$ [Beyersdorff, Datta, Krebs, Mahajan, Scharfenberger-Fabian, Sreenivasaiah, Thomas and Vollmer, 2013] to $\Omega(\sqrt{\log n})$, leaving only a quartic gap from the best upper bound of $O(\log^2 n)$.Sun, 14 May 2023 14:04:25 +0300https://eccc.weizmann.ac.il/report/2023/071