Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields
cs.CC
Submitted: 2026-11-02
Updated: 2026-11-02
Terminology
Sources
- Bias vs structure of polynomials in large fields, and applications in information theory
- Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_p$
- Ranges of polynomials control degree ranks of Green and Tao over finite prime fields
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?