Six-Author Paper Proves Exponential Correlation Bounds for Polynomials, Yields Polylog-Seed PRGs
Pooyahat · x · 2026-10-14
Pooya Hatami et al. (with Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola) released a revised ECCC paper proving the XOR of k majorities on disjoint blocks of ℓ bits correlates at most (4d/√ℓ)^k with any Boolean degree-d polynomial over an arbitrary field.
- This yields explicit PRGs with seed length d²·polylog(n/ε) fooling such polynomials.
- Results extend to small AC⁰[q] circuits for any fixed prime power q.
- The authors state the results resolve several long-standing open questions in circuit complexity and pseudorandomness.
- The revision generalizes the main results to all finite fields and adds new applications.
More from Research
- Laude Institute launches FrontierCS 2: agents must beat deleted paper contributions blind — lateinteraction · 2026-10-23
- RFD4-Proteina's 'underrated' docs detail partial diffusion for protein redesign — AllThingsApx · 2026-10-23
- MPI-Sec PhD Thesis on Vulnerability Detection Benchmarks Includes Pre-LLM Classic "Top Score on the Wrong Exam" — mboehme_ · 2026-10-23
- LiveNerf's 29-day data finds no nerfing of Claude Opus 5.5 — TheOnlyVibemaster · 2026-10-23
- New paper makes 9 falsifiable predictions toward a major AI-enabled terror attack by 2027-2028 — StephenLCasper · 2026-10-23
- HumanoidPose recovers humanoid robots' full-body joint states from RGB video alone — cholz · 2026-10-23