pith. sign in

arxiv: 2605.00995 · v1 · submitted 2026-05-01 · 💻 cs.CC · math.CO

On Sampling Lower Bounds for Polynomials

Mohammad Mahdi Khodabandeh , Igor Shinkar This is my paper

Pith reviewed 2026-05-09 14:29 UTC · model grok-4.3

classification 💻 cs.CC math.CO
keywords low-degree polynomialssampling lower boundstotal variation distanceproduct Bernoulli distributionbias lemmaF_2structural theoremcomplexity of distributions
0
0 comments X

The pith

Any distribution generated by n degree-d polynomials over F_2 is at least 1-o(1) far in total variation from the product of n independent Ber(1/3) random variables.

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

The paper establishes lower bounds on how well low-degree polynomial functions can sample from a product distribution. Specifically, evaluating n polynomials of fixed degree d on a uniform random input from F_2^m produces a distribution on {0,1}^n whose total variation distance to Ber(1/3) raised to n is 1 minus a small term that goes to zero only as n increases. This holds because each individual polynomial cannot have its acceptance probability too close to 1/3, and this bias propagates. A reader would care because it shows fundamental limitations of algebraic methods in generating nearly independent biased bits, extending known barriers from circuit and local samplers.

Core claim

When P is an n-tuple of degree-d polynomials from F_2^m to F_2, the induced distribution on {0,1}^n satisfies ||P - Ber(1/3)^⊗n||_TV = 1 - o_n(1) for any constant d. For d=1 the distance is at least 1 - exp(-Omega(n)), for d=2 at least 1-exp(-Omega(log n / log log n)), and for d=3 at least 1-exp(-Omega(sqrt(log log n))). This relies on proving that for any degree-d polynomial Q, Pr[Q(X)=1] is bounded away from 1/3 by some absolute constant delta_d >0.

What carries the argument

The structural theorem for low-degree polynomials over F_2 stating that any biased degree-d polynomial can be written as a function of a small number of degree-(d-1) polynomials, used to bound the bias inductively.

Load-bearing premise

The structural theorem that any biased degree-d polynomial over F_2 can be written as a function of a small number of degree-(d-1) polynomials holds.

What would settle it

An explicit construction of degree-d polynomials P_1 to P_n where the output distribution has total variation distance o(1) to Ber(1/3)^⊗n for large n.

Figures

Figures reproduced from arXiv: 2605.00995 by Igor Shinkar, Mohammad Mahdi Khodabandeh.

Figure 1
Figure 1. Figure 1: A win-win scenario for sampling lower bound. view at source ↗
read the original abstract

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $P = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: draw $X$ uniformly at random from $\mathbb{F}_2^m$ and output $(P_1(X),\dots, P_n(X)) \in \{0,1\}^n$. We show that when $P$ is defined by polynomials of degree $d$, the total variation distance of $P$ from the product distribution $\mathrm{Ber}(1/3)^{\otimes n}$ is $1-o_n(1)$, where $o_n(1)$ is a vanishing function of $n$ for any constant degree $d$. For small values of $d$, we show the following concrete bounds. (i) For $d=1$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(n))$. (ii) For $d=2$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(\log(n)/\log\log(n)))$. (iii) For $d=3$ we have $\|P-\mathrm{Ber}(1/3)^{\otimes n}\|_{TV} \geq 1-\exp(-\Omega(\sqrt{\log\log(n)}))$. Our results extend the recent lower bound results for sampling distributions, which have mostly focused on local samplers, small depth decision trees, and small depth circuits. As part of our proof, we establish the following result, that may be of independent interest: for any degree-$d$ polynomial $P\colon\mathbb{F}_2^m \to \mathbb{F}_2$ it holds that $\Pr_X[P(X) = 1]$ is bounded away from $1/3$ by some absolute constant $\delta = \delta_d>0$. Although the statement may seem obvious, we are not aware of an elementary proof of this. The proof techniques rely on the structural results for low degree polynomials, saying that any biased polynomial of degree $d$ can be written as a function of a small number of polynomials of degree $d-1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims that any distribution over {0,1}^n generated by n degree-d polynomials over F_2 (evaluated on uniform random input) has total variation distance 1-o_n(1) from Ber(1/3)^⊗n for constant d. Explicit quantitative lower bounds are stated for d=1 (1-exp(-Ω(n))), d=2 (1-exp(-Ω(log n / log log n))), and d=3 (1-exp(-Ω(√log log n))). A supporting bias lemma asserts that no degree-d polynomial P satisfies |Pr[P=1]-1/3| < δ_d for a positive constant δ_d = δ_d > 0; the lemma is proved by invoking structural theorems that express biased degree-d polynomials as functions of a bounded number of degree-(d-1) polynomials, which in turn limits the possible bias values and enables an inductive argument on d to obtain the TV bounds.

Significance. If the central claims hold, the work extends the line of sampling lower bounds (building on Viola 2012) from local functions, decision trees, and circuits to constant-degree polynomial samplers, showing that even this model cannot approximate the target product distribution. The bias lemma is of independent interest for the analysis of Boolean functions, as it rules out bias exactly 1/3 for low-degree polynomials via structural decomposition rather than direct calculation. The explicit rates for small d are a concrete strength, and the argument is internally consistent once the structural theorems are applied to the specific bias target.

minor comments (3)
  1. The abstract states that an elementary proof of the bias lemma was previously unknown; the manuscript should briefly note in the introduction or §1 why the structural-theorem approach qualifies as non-elementary or what alternative elementary routes were considered.
  2. The quantitative bounds for d=2 and d=3 arise from a recurrence on structure depth; a short paragraph or table summarizing the recurrence parameters and how they yield the stated exponents would improve readability.
  3. Notation: the o_n(1) term is defined as vanishing for fixed d as n→∞; adding an explicit sentence in the introduction confirming that δ_d is independent of n and m would prevent any ambiguity about uniformity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. Their summary correctly captures the main results on total variation distance lower bounds for constant-degree polynomial samplers from Ber(1/3)^⊗n, the explicit quantitative bounds for small d, and the supporting bias lemma for low-degree polynomials over F_2.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central derivation proceeds by invoking the known structural theorem on low-degree polynomials (any biased degree-d polynomial is a function of O(1) degree-(d-1) polynomials) to prove the bias lemma that Pr[P=1] is bounded away from 1/3 by a d-dependent constant δ_d>0; this lemma is then used inductively to obtain the quantitative TV lower bounds 1-o_n(1) (with explicit rates for d=1,2,3). The structural theorem is external prior work, the bias lemma is newly proved from it rather than assumed, and the TV claim follows from the resulting marginal constraints without any parameter fitting, self-definition, or reduction of the target quantity to the input by construction. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a single domain assumption from prior literature; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Any biased polynomial of degree d over F_2 can be expressed as a function of a small number of degree-(d-1) polynomials.
    Invoked explicitly in the proof technique section of the abstract to establish the bias bound away from 1/3.

pith-pipeline@v0.9.0 · 5788 in / 1440 out tokens · 37532 ms · 2026-05-09T14:29:16.441297+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Annals of Combinatorics , volume=

    The inverse conjecture for the Gowers norm over finite fields in low characteristic , author=. Annals of Combinatorics , volume=. 2012 , publisher=

    work page 2012

  2. [2]

    Foundations and Trends

    Higher-order fourier analysis and applications , author=. Foundations and Trends

    work page

  3. [3]

    1996 , place=

    Finite Fields , author=. 1996 , place=

    work page 1996

  4. [4]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    On the structure of cubic and quartic polynomials , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    work page

  5. [5]

    Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Algorithmic regularity for polynomials and applications , author=. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2014 , organization=

    work page 2014

  6. [6]

    Electronic Colloquium on Computational Complexity (ECCC) , year =

    Constant-time source decoding , author =. Electronic Colloquium on Computational Complexity (ECCC) , year =

    work page

  7. [7]

    2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=

    Worst case to average case reductions for polynomials , author=. 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2008 , organization=

    work page 2008

  8. [8]

    Contributions to Discrete Mathematics , volume =

    The distribution of polynomials over finite fields, with applications to the Gowers norms , author=. Contributions to Discrete Mathematics , volume =. 2009 , doi =

    work page 2009

  9. [9]

    38th Computational Complexity Conference (CCC 2023) , pages=

    New sampling lower bounds via the separator , author=. 38th Computational Complexity Conference (CCC 2023) , pages=. 2023 , organization=

    work page 2023

  10. [10]

    SIAM Journal on Computing , volume=

    The complexity of distributions , author=. SIAM Journal on Computing , volume=. 2012 , publisher=

    work page 2012

  11. [11]

    arXiv preprint arXiv:2511.14127 , year=

    Symmetric Distributions from Shallow Circuits , author=. arXiv preprint arXiv:2511.14127 , year=

    work page arXiv

  12. [12]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    work page

  13. [13]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Locally sampleable uniform symmetric distributions , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    work page

  14. [14]

    17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =

    Unconditional quantum advantage for sampling with shallow circuits , author=. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages =. 2026 , volume =. doi:10.4230/LIPIcs.ITCS.2026.17 , annote =

    work page doi:10.4230/lipics.itcs.2026.17 2026

  15. [15]

    15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=

    Sampling, flowers and communication , author=. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=. 2024 , organization=

    work page 2024

  16. [16]

    Journal of the London Mathematical Society , volume=

    Intersection theorems for systems of sets , author=. Journal of the London Mathematical Society , volume=. 1960 , publisher=

    work page 1960

  17. [17]

    Information and control , volume=

    On the weight enumeration of weights less than 2.5 d of Reed—Muller codes , author=. Information and control , volume=. 1976 , publisher=

    work page 1976

  18. [18]

    IEEE Transactions on Information Theory , volume=

    On the weight structure of Reed-Muller codes , author=. IEEE Transactions on Information Theory , volume=. 1970 , publisher=

    work page 1970

  19. [19]

    IEEE transactions on information theory , volume=

    Weight distribution and list-decoding size of reed--muller codes , author=. IEEE transactions on information theory , volume=. 2012 , publisher=

    work page 2012

  20. [20]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    Inverse conjecture for the Gowers norm is false , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    work page

  21. [21]

    Mathematical systems theory , volume=

    Parity, circuits, and the polynomial-time hierarchy , author=. Mathematical systems theory , volume=. 1984 , publisher=

    work page 1984

  22. [22]

    Annals of pure and applied logic , volume=

    Ajtai, Mikl. Annals of pure and applied logic , volume=. 1983 , publisher=

    work page 1983

  23. [23]

    Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages=

    Almost optimal lower bounds for small depth circuits , author=. Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages=

    work page

  24. [24]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    Locality bounds for sampling hamming slices , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    work page

  25. [25]

    Approximation, Randomization, and Combinatorial Optimization

    Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.36 , annote =

    work page doi:10.4230/lipics.approx/random.2023.36 2023

  26. [26]

    13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages=

    The space complexity of sampling , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages=. 2022 , organization=

    work page 2022

  27. [27]

    ACM Transactions on Computation Theory (TOCT) , volume=

    A lower bound for sampling disjoint sets , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2020 , publisher=

    work page 2020

  28. [28]

    SIAM Journal on Computing , volume=

    Sampling lower bounds: boolean average-case and permutations , author=. SIAM Journal on Computing , volume=. 2020 , publisher=

    work page 2020

  29. [29]

    ACM Transactions on Computation Theory (TOCT) , volume=

    Quadratic maps are hard to sample , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2016 , publisher=

    work page 2016

  30. [30]

    ACM Transactions on Computation Theory (TOCT) , volume=

    Extractors and lower bounds for locally samplable sources , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2012 , publisher=

    work page 2012

  31. [31]

    2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=

    Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    work page 2012

  32. [32]

    2011 IEEE 26th Annual Conference on Computational Complexity , pages=

    Bounded-depth circuits cannot sample good codes , author=. 2011 IEEE 26th Annual Conference on Computational Complexity , pages=. 2011 , organization=

    work page 2011