Pith. sign in

REVIEW 46 references

Locally Sampleable Uniform Symmetric Distributions

T0 review · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Constant-depth Boolean circuits that nearly sample a uniform symmetric distribution must be close to zeros, ones, both extremes, evens, odds, or all strings.

arxiv 2411.08183 v2 pith:MN44SDYV submitted 2024-11-12 cs.CC

Daniel M. Kane , Anthony Ostuni , Kewen Wu This is my paper · ORCID
classification cs.CC
keywords uniformdistributionstringssymmetricbitsbooleandistributionshamming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Imagine a simple circuit whose each output bit is computed from only a few input bits, say two or three. Such circuits are called NC^0. If you feed them random bits, they output a random-looking string. A natural question is which probability distributions over n-bit strings can these circuits generate approximately. This paper focuses on symmetric distributions, where all strings with the same number of 1s are equally likely. For instance, the uniform distribution over strings with an even number of 1s can be generated easily by taking XORs of adjacent bits.

The authors prove that this example is essentially the limit. If an NC^0 circuit's output is close to any symmetric distribution, then it must be close to one of six: all zeros, all ones, the two extremes together, even-weight strings, odd-weight strings, or all strings. No other symmetric distribution, such as strings with exactly half 1s or strings with weights divisible by 3, can be approximated.

The proof uses two main ideas. First, a hypergraph decomposition shows that, after ignoring a few important input bits, the outputs split into many independent small groups. This imports methods from a prior paper by the same authors. Second, a new local limit theorem proves that the total number of 1s in the output behaves like a binomial distribution, up to parity. A clever pairing argument then shows that any symmetric distribution different from the six special ones would be far from any such output.

Extended reading notes

Core claim

Theorem 4.1: Let d be fixed and f:{0,1}^m -> {0,1}^n be a d-local function with n sufficiently large. If ||f(U^m)-D_Ψ||_{TV} ≤ ε for some set of allowed Hamming weights Ψ, then ||f(U^m)-D||_{TV} ≤ O(ε) for some D in {zeros, ones, zerones, evens, odds, all}. In particular, this confirms Conjecture 1.1 of Filmus, Leigh, Riazanov, and Sokolov.

Load-bearing premise

The central-regime proof relies crucially on the hypergraph elimination lemma of KOW24, Proposition 5.20 (restated as Corollary 5.9), which asserts that from a degree-d hypergraph one can delete o(n) edges and retain Ω_d(n) vertices with pairwise non-adjacent neighborhoods of size O_d(1). If this structural claim failed, the independence and anticoncentration arguments underpinning Proposition 4.9 and Lemma 5.5 would collapse. This is an external result by two of the current authors and is not re-proven in the paper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper leans on several non-trivial external theorems, especially the hypergraph elimination lemma and Hamming-slice lower bounds from KOW24 and FLRS23, which are special cases of the conjecture rather than instances of its conclusion. It introduces no new unproven entities. The remaining axioms are standard probabilistic and combinatorial inequalities.

assumptions (5)
  • domain assumption Hypergraph elimination lemma (KOW24 Prop 5.20): there is a set of o(n) edges whose removal leaves Omega_d(n) pairwise non-adjacent neighborhoods of size O_d(1).
    Used in Sections 2.1 and 5.2 (Corollary 5.9) to decompose f into independent output neighborhoods.
  • domain assumption Slice sampling lower bounds (FLRS23 Thm 1.2 and KOW24 Thm 5.10): any d-local function is 1 - O_d(n^{-1/2}) far from D_{k} for 1 <= k <= n-1.
    Used as Theorem 4.6 in the tail regime proof.
  • domain assumption Bounded independence fools halfspaces (DGJ+10): k-wise independent distributions approximate threshold functions on n bits within O(log k / sqrt(k)).
    Used as Theorem 5.3 to prove the Kolmogorov bound.
  • domain assumption XOR / randomization lemma for low-degree F2 polynomials (CHH+20 Thm 3.1): few random input bits can randomize the parity of a degree-d polynomial.
    Used as Theorem 5.4 to handle parity in Lemma 5.2.
  • standard math Standard inequalities: Hoeffding, Chernoff, Chebyshev, hypercontractivity, anticoncentration, binomial coefficient bounds.
    Throughout Sections 3, 4, and 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Locally Sampleable Uniform Symmetric Distributions." pith.science (2026). https://pith.science/paper/MN44SDYV

@misc{pith2026241108183,
  author       = {Pith},
  title        = {Pith review of: Locally Sampleable Uniform Symmetric Distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MN44SDYV}},
  note         = {Machine review of arXiv:2411.08183}
}
abstract

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{0,1\}^m\to\{0,1\}^n$ be a Boolean function where each output bit of $f$ depends only on $O(1)$ input bits. Assume the output distribution of $f$ on uniform input bits is close to a uniform distribution $D$ with a symmetric support. We show that $D$ is essentially one of the following six possibilities: (1) point distribution on $0^n$, (2) point distribution on $1^n$, (3) uniform over $\{0^n,1^n\}$, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 42 canonical work pages

  1. [1]

    Random oracles separate PSPACE from the polynomial-time hierarchy

    L \'a szi \'o Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters , 26(1):51--53, 1987

    work page 1987

  2. [2]

    Verifying proofs in constant depth

    Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer. Verifying proofs in constant depth. ACM Transactions on Computation Theory (TOCT) , 5(1):1--23, 2013

    work page 2013

  3. [3]

    Quantum advantage with shallow circuits

    Sergey Bravyi, David Gosset, and Robert K \"o nig. Quantum advantage with shallow circuits. Science , 362(6412):308--311, 2018

    2018

  4. [4]

    Quantum advantage with noisy shallow circuits

    Sergey Bravyi, David Gosset, Robert K \"o nig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics , 16(10):1040--1045, 2020

    2020

  5. [5]

    Large deviation bounds for decision trees and sampling lower bounds for AC0 -circuits

    Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0 -circuits. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 101--110. IEEE, 2012

    work page 2012

  6. [6]

    One-way functions and circuit complexity

    Ravi B Boppana and Jeffrey C Lagarias. One-way functions and circuit complexity. Information and Computation , 74(3):226--240, 1987

    work page 1987

  7. [7]

    \'E tude des coefficients de fourier des fonctions de L^ p (G)

    Aline Bonami. \'E tude des coefficients de fourier des fonctions de L^ p (G) . In Annales de l'institut Fourier , volume 20, pages 335--402, 1970

    work page 1970

  8. [8]

    Estimates for B ezout coefficients

    Fran o is Brunault. Estimates for B ezout coefficients. MathOverflow, 2012. URL:https://mathoverflow.net/q/108723 (version: 2012-10-05)

    work page 2012

Show all 46 references
  1. [9]

    The space complexity of sampling

    Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. In 13th Innovations in Theoretical Computer Science Conference,(ITCS 2022) , 2022

    2022

  2. [10]

    XOR lemmas for resilient functions against polynomials

    Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman. XOR lemmas for resilient functions against polynomials. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 234--246, 2020

    2020

  3. [11]

    Extractors for near logarithmic min-entropy

    Gil Cohen and Leonard J Schulman. Extractors for near logarithmic min-entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 178--187. IEEE, 2016

    2016

  4. [12]

    Elements of information theory, 2006

    Thomas M Cover and Joy A Thomas. Elements of information theory, 2006

    2006

  5. [13]

    Explicit two-source extractors and resilient functions

    Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 670--683, 2016

    2016

  6. [14]

    Bounded independence fools halfspaces

    Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM Journal on Computing , 39(8):3441--3462, 2010

    2010

  7. [15]

    Extractors and lower bounds for locally samplable sources

    Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. ACM Transactions on Computation Theory (TOCT) , 4(1):1--21, 2012

    2012

  8. [16]

    Sampling and certifying symmetric functions

    Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and certifying symmetric functions. In Approximation, Randomization, and Combinatorial Optimization. (APPROX/RANDOM) , 2023

    2023

  9. [17]

    Are there a few input bits that randomize the output of an F _2 polynomial? MathOverflow, 2023

    Jason Gaitonde. Are there a few input bits that randomize the output of an F _2 polynomial? MathOverflow, 2023. URL:https://mathoverflow.net/q/460879 (version: 2023-12-22)

    2023

  10. [18]

    Verifying and decoding in constant depth

    Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N Rothblum. Verifying and decoding in constant depth. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 440--449, 2007

    2007

  11. [19]

    Range avoidance for constant-depth circuits: Hardness and algorithms

    Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. Range avoidance for constant-depth circuits: Hardness and algorithms. arXiv preprint arXiv:2303.05044 , 2023

    2023 arXiv

  12. [20]

    Range avoidance for low-depth circuits and connections to pseudorandomness

    Venkatesan Guruswami, Xin Lyu, and Xiuhan Wang. Range avoidance for low-depth circuits and connections to pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) . Schloss-Dagstuhl-Leibniz Zentrum f \"u ...

    2022

  13. [21]

    A lower bound for sampling disjoint sets

    Mika G \"o \"o s and Thomas Watson. A lower bound for sampling disjoint sets. ACM Transactions on Computation Theory (TOCT) , 12(3):1--13, 2020

    2020

  14. [22]

    Fast parallel generation of random permutations

    Torben Hagerup. Fast parallel generation of random permutations. In Automata, Languages and Programming: 18th International Colloquium Madrid, Spain, July 8--12, 1991 Proceedings 18 , pages 405--416. Springer, 1991

    1991

  15. [23]

    Computational limitations for small depth circuits

    Johan H stad. Computational limitations for small depth circuits . PhD thesis, Massachusetts Institute of Technology, 1986

    1986

  16. [24]

    Random generation of combinatorial structures from a uniform distribution

    Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical computer science , 43:169--188, 1986

    1986

  17. [25]

    A structure theorem for poorly anticoncentrated polynomials of G aussians and applications to the study of polynomial threshold functions

    Daniel M Kane. A structure theorem for poorly anticoncentrated polynomials of G aussians and applications to the study of polynomial threshold functions. 2017

    2017

  18. [26]

    A polynomial restriction lemma with applications

    Valentine Kabanets, Daniel M Kane, and Zhenjian Lu. A polynomial restriction lemma with applications. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 615--628, 2017. Available at https://cseweb.ucsd.edu/ dakane/PTFblockRestriction.pdf

    2017

  19. [27]

    Small depth proof systems

    Andreas Krebs, Nutan Limaye, Meena Mahajan, and Karteek Sreenivasaiah. Small depth proof systems. ACM Transactions on Computation Theory (TOCT) , 9(1):1--26, 2016

    2016

  20. [28]

    Locality bounds for sampling H amming slices

    Daniel M Kane, Anthony Ostuni, and Kewen Wu. Locality bounds for sampling H amming slices. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1279--1286, 2024. Available at https://arxiv.org/abs/2402.14278

    2024 arXiv

  21. [29]

    Sum of the first k binomial coefficients for fixed n

    Michael Lugo. Sum of the first k binomial coefficients for fixed n . MathOverflow, 2017. URL:https://mathoverflow.net/q/17236 (version: 2017-10-01)

    2017

  22. [30]

    Bounded-depth circuits cannot sample good codes

    Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. In 2011 IEEE 26th Annual Conference on Computational Complexity , pages 243--251. IEEE, 2011

    2011

  23. [31]

    Converting high probability into nearly-constant time—with applications to parallel hashing

    Yossi Matias and Uzi Vishkin. Converting high probability into nearly-constant time—with applications to parallel hashing. In Proceedings of the twenty-third annual ACM symposium on Theory of Computing , pages 307--316, 1991

    1991

  24. [32]

    On the range avoidance problem for circuits

    Hanlin Ren, Rahul Santhanam, and Zhikun Wang. On the range avoidance problem for circuits. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 640--650. IEEE, 2022

    2022

  25. [33]

    Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions

    Ronen Shaltiel and Jad Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 2028--2038, 2024

    2024

  26. [34]

    Upper estimates of maximum probability for sums of independent random vectors

    Nikolai G Ushakov. Upper estimates of maximum probability for sums of independent random vectors. Theory of Probability & Its Applications , 30(1):38--49, 1986

    1986

  27. [35]

    Bit-probe lower bounds for succinct data structures

    Emanuele Viola. Bit-probe lower bounds for succinct data structures. SIAM Journal on Computing , 41(6):1593, 2012

    2012

  28. [36]

    The complexity of distributions

    Emanuele Viola. The complexity of distributions. SIAM Journal on Computing , 41(1):191--218, 2012

    2012

  29. [37]

    Extractors for T uring-machine sources

    Emanuele Viola. Extractors for T uring-machine sources. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 663--671. Springer, 2012

    2012

  30. [38]

    Extractors for circuit sources

    Emanuele Viola. Extractors for circuit sources. SIAM Journal on Computing , 43(2):655--672, 2014

    2014

  31. [39]

    Quadratic maps are hard to sample

    Emanuele Viola. Quadratic maps are hard to sample. ACM Transactions on Computation Theory (TOCT) , 8(4):1--4, 2016

    2016

  32. [40]

    Sampling lower bounds: boolean average-case and permutations

    Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM Journal on Computing , 49(1):119--137, 2020

    2020

  33. [41]

    New sampling lower bounds via the separator

    Emanuele Viola. New sampling lower bounds via the separator. In 38th Computational Complexity Conference (CCC 2023) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik. Available at https://eccc.weizmann.ac.il/report/2021/073/, 2023

    2023

  34. [42]

    Binary entropy function --- W ikipedia , the free encyclopedia

    Wikipedia. Binary entropy function --- W ikipedia , the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Binary\ [Online; accessed 04-December-2023]

    2023

  35. [43]

    Binomial coefficient --- W ikipedia , the free encyclopedia

    Wikipedia. Binomial coefficient --- W ikipedia , the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Binomial\ [Online; accessed 15-December-2023]

    2023

  36. [44]

    Bézout's identity --- W ikipedia , the free encyclopedia

    Wikipedia. Bézout's identity --- W ikipedia , the free encyclopedia. http://en.wikipedia.org/w/index.php?title=B\ [Online; accessed 05-December-2023]

    2023

  37. [45]

    Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

    Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 515--526, 2019

    2019

  38. [46]

    Unconditional quantum advantage for sampling with shallow circuits

    Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits. arXiv preprint arXiv:2301.00995 , 2023

    2023 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.