Pseudorandom generators for polynomials¶
Pseudorandom generators for low-degree polynomials are a particular instance of pseudorandom generators for statistical tests, where the statistical tests considered are evaluations of low-degree polynomials.
Core Idea¶
Pseudorandom generators for polynomials is treated here as the recurring mathematics, logic, and statistics identity summarized by this source-grounded definition: Pseudorandom generators for low-degree polynomials are a particular instance of pseudorandom generators for statistical tests, where the statistical tests considered are evaluations of low-degree polynomials. In theoretical computer science, a pseudorandom generator for low-degree polynomials is an efficient procedure that maps a short truly random seed to a longer pseudorandom string in such a way that low-degree polynomials cannot distinguish the output distribution of the generator from the truly random distribution.
Scope of Application¶
-
Construction. The case d=1 corresponds to pseudorandom generators for linear functions and is solved by small-bias generators.
-
Definition. In other words, for every such polynomial p(x1,\dots,xn) , the statistical distance between the distributions p(Un) and p(G(U\ell)) is at most a small \epsilon , where.
-
Construction. For example, the construction of achieves a seed length of \ell= \log n + O(\log (\epsilon^{-1})) , which is optimal up to constant factors.
-
Construction. conjectured that the sum of small-bias generators fools low-degree polynomials and were able to prove this under the Gowers inverse conjecture.
-
Construction. proved unconditionally that the sum of 2^d small-bias spaces fools polynomials of degree d .
Clarity¶
A clear use of Pseudorandom generators for polynomials names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is Pseudorandom generators for low-degree polynomials are a particular instance of pseudorandom generators for statistical tests, where the statistical tests considered are evaluations of low-degree polynomials.
Manages Complexity¶
Pseudorandom generators for polynomials compresses multiple mathematics, logic, and statistics details into a stable diagnostic relation. The source shows both the central mechanism—a pseudorandom generator G: \mathbb{F}^\ell \rightarrow \mathbb{F}^n for polynomials of degree d over a finite field \mathbb F is an efficient procedure that maps a sequence of \ell field elements to a sequence of n field elements such that any n -variate polynomial.
Abstract Reasoning¶
- Type the carrier. Identify the mathematics, logic, and statistics entities to which the claim applies.
- State the relation. Use the source-grounded identity: Pseudorandom generators for low-degree polynomials are a particular instance of pseudorandom generators for statistical tests, where the statistical tests considered are evaluations of low-degree polynomials.
- Check operation and conditions. That is, evaluating any low-degree polynomial at a point determined by the pseudorandom string is statistically close to evaluating the same polynomial at a point that is chosen uniformly at random. 4.
Knowledge Transfer¶
Within the home domain. Knowledge about Pseudorandom generators for polynomials transfers literally when a new case preserves the same carrier type, relation, and recognition test. The case d=1 corresponds to pseudorandom generators for linear functions and is solved by small-bias generators. In other words, for every such polynomial p(x1,\dots,xn) , the statistical distance between the distributions p(Un) and p(G(U\ell)) is at most a small \epsilon , where Uk is the uniform distribution over \mathbb{F}^k . Beyond the home domain. No canonical parent is asserted for Pseudorandom generators for polynomials.
Neighborhood in Abstraction Space¶
Pseudorandom generators for polynomials sits in a crowded region of the domain-specific corpus (40th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Polynomials & Algebraic Invariants (20 abstractions)
Nearest neighbors
- Laurent Polynomial — 0.88
- Invariant polynomial — 0.87
- NC (complexity) — 0.87
- Big O in probability notation — 0.87
- Randomness extractor — 0.87
Computed from structural-signature embeddings · 2026-10-08