Polynomial Regularity for Pseudorandomness and Counting

This direction is split into other directions: influence-based partitioning. Its last version stays readable and citable here.

Version 1 of 127 papers36 conceptsfrozen 2026-10-04

Polynomial Threshold Functions (PTFs) are Boolean functions of the form $f(x) = \text{sgn}(P(x))$, where $P$ is a multivariate polynomial. They are fundamental objects in circuit complexity and learning theory, but they are notoriously difficult to analyze because the sign function is discontinuous and the polynomial interactions are global.

The core insight shared across this research direction is that any complex polynomial can be decomposed into a "structured" part and a "pseudorandom" part. This structural decomposition, often called a Polynomial Regularity Lemma, allows researchers to replace hard discrete problems with more manageable continuous ones.

The Invariance Principle and Regularity

The primary reason we care if a polynomial is "regular" is the Invariance Principle. In essence, if no single variable in a polynomial $P$ has a disproportionate "influence" on the outcome, then the distribution of $P(x)$ when $x$ is chosen from a Boolean hypercube $\{-1, 1\}^n$ is nearly identical to its distribution when $x$ is chosen from a multidimensional Gaussian.

This is a powerful tool for derandomization. As Ilias Diakonikolas, Daniel Kane, and Jelani Nelson demonstrated in Bounded Independence Fools Degree-2 Threshold Functions, if a degree-2 polynomial is regular, it can be "fooled" by $k$-wise independent distributions. This means we don't need "true" randomness to estimate the behavior of the function; a much simpler, limited form of randomness suffices.

Decomposing via Decision Trees

What happens if a polynomial is not regular? If a few variables have high influence, the Invariance Principle fails. The solution, pioneered by Raghu Meka and David Zuckerman in Pseudorandom Generators for Polynomial Threshold Functions, is to use a decision tree decomposition.

The strategy works as follows:

  1. Identify Influential Variables: Find the variables that exert the most control over the polynomial's value.
  2. Branch: Create a decision tree by fixing the values of these influential variables.
  3. Recurse: In each branch, you are left with a new polynomial of the remaining variables.
  4. Reach Regularity: Eventually, you reach "leaf" nodes where the remaining polynomial is either almost constant or "regular" (no variable is dominant).

This decomposition ensures that every PTF can be viewed as a collection of regular components. Anindya De, Ilias Diakonikolas, and Rocco A. Servedio used this exact structure in Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions to create the first efficient deterministic algorithms for counting the number of satisfying assignments to a degree-2 PTF.

Higher Order Fourier Analysis

For higher-degree polynomials or functions over finite fields, simple "influence" is not enough to capture structure. Researchers like Arnab Bhattacharyya and Shachar Lovett utilize higher-order Fourier analysis to achieve a similar decomposition.

In papers like Testing Low Complexity Affine-Invariant Properties, they prove a "Super Decomposition Theorem." This theorem splits a function into three parts:

  • Structured Component: A function of a few low-degree polynomials.
  • Pseudorandom Component: A part with a very small Gowers norm (meaning it has no correlation with any low-degree structure).
  • Error Term: A small part that can be ignored.

This tripartite view allows for the testing of complex algebraic properties. If a property is "affine-invariant" (it doesn't change if you shift the coordinates), you can check if a function has that property by querying only a constant number of points, as shown in Every locally characterized affine-invariant property is testable.

Settling Conjectures and Algorithmic Tools

The power of these regularity lemmas is best seen in their ability to settle long-standing problems. Daniel Kane applied these decomposition techniques in The Correct Exponent for the Gotsman-Linial Conjecture to prove that the average sensitivity of a degree-$d$ PTF is $O(\sqrt{n} \cdot \text{polylog}(n))$, confirming the "correct exponent" for the complexity of these functions.

Furthermore, these are not just existential proofs. Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani developed Algorithmic regularity for polynomials and applications, showing that these decompositions can be computed efficiently. This turns a theoretical structural result into a practical tool for tasks like decoding Reed-Muller codes and performing worst-case to average-case reductions.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_polynomial_regularity_for_pseudorandomne_a1a83715,
  title = {Polynomial Regularity for Pseudorandomness and Counting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-regularity-for-pseudorandomness-and-counting/rdr_a1a837159bfc4768bb8dfd432e284878},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_polynomial_regularity_for_pseudorandomne_a1a83715_v1,
  title = {Polynomial Regularity for Pseudorandomness and Counting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-regularity-for-pseudorandomness-and-counting/rdr_a1a837159bfc4768bb8dfd432e284878/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}