Pseudorandom bits for low degree modular polynomials

Pseudorandom bits for low degree modular polynomials

Title history
  • Pseudorandom bits for low degree modular polynomials — observed on 20261101-0403 UTC (YouTube)

by Tejas Nareddy · View the channel on PSI

Formal & Physical Sciences Science — General & History GPResearch and information: generalGPJCoding theory and cryptology
🎙 Tejas Nareddy 👥 78K 📅 October 31, 2026 ⏱ 31 min 👁 694 📄 original study 🧭 2026-11-01
Available in: English (current) Français

Keywords

pseudorandom generatorlow-degree polynomialmodular arithmeticcoin problemgroup branching program

Summary

The talk, given by Tejas Nareddy, presents a joint work with Chin Ho Lee, Shachar Lovett, and Emanuele Viola on constructing pseudorandom generators (PRGs) for low-degree modular polynomials. These polynomials are functions that take bits as input but compute arithmetic modulo a fixed integer m. The main result is an explicit PRG with seed length O(log n/ε) that ε-fools all degree-d modular polynomials over any integer modulus m, for fixed d and m. This extends previous work that only achieved optimal dependence for prime moduli. The talk also discusses an application to derandomizing nilpotent group branching programs. The proof combines techniques from small-bias distributions, the coin problem lower bound, and a new Fourier growth bound, along with a framework for pseudorandomness plus noise. Key steps include domain reduction and modulus reduction to transfer constructions from prime fields to composite moduli. The talk concludes with an open problem: achieving polynomial degree (in n) for composite moduli, as current methods are limited to degree O(log n).

164 words

Critical Evaluation

Value of the Information & Strength of the Argument

The presentation offers significant value by resolving a key question in derandomization: constructing optimal-seed PRGs for modular polynomials with arbitrary moduli. The argumentation is systematic and clear: it starts with definitions, reviews prior work, identifies gaps, and then builds the result stepwise using known tools and novel analyses. The speaker explicitly addresses audience questions, clarifying subtleties such as the distinction between prime and composite moduli, and the limitations of existing techniques. The logic is solid, with the proof sketch giving enough details to follow the high-level reasoning without overwhelming the audience. The use of the coin problem and Fourier growth bounds is well-motivated, and the transitions between ideas are smooth. The claimed result is theoretically important and plausible, supported by formal arguments that are standard in the field.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous: it builds on a body of established work (e.g., Naor–Naor, Bogdanov–Viola, Lovett, Viola, LRTV, and others) and cites them appropriately. The speaker acknowledges the precise contributions of prior works and parameter boundaries. The title is perfectly aligned with the content, as the entire talk is dedicated to pseudorandom bits for low-degree modular polynomials. No extraneous material is presented. The presence of a technical audience discussion further validates the depth and correctness of the claims. The only minor point is that the talk does not provide a full formal proof, but that is typical for a workshop presentation; the outline is sufficient for experts. Overall, the sources and the title are fully consistent with the scholarly standard expected at the Simons Institute.

269 words

Title / Content Match

The title accurately reflects the content: the talk presents a pseudorandom generator for low-degree modular polynomials, matching the title precisely.

Quality & Reliability

9/10

Research talk presented at the Simons Institute, a leading venue for theoretical computer science. The speaker is an established researcher, and the content is technically rigorous with clear proofs and references to prior work. No obvious errors or unsubstantiated claims; the talk is well-structured and detailed.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

This work provides the first PRGs for low-degree modular polynomials over arbitrary composite moduli with optimal seed length (log n/ε). It achieves a nearly optimal dependence on both n and ε, improving over prior constructions that had exponential towers in degree or only worked for prime moduli. The proof introduces a new Fourier growth bound for polynomials over composite moduli and develops techniques of domain reduction and modulus reduction that may be reusable in other derandomization contexts. Additionally, the result implies explicit PRGs for nilpotent group branching programs with improved seed length.

Pour aller plus loin :

  • Derandomization — General context of making randomized algorithms deterministic.
  • Pseudorandom generator — Formal definition and role in complexity theory.
  • Branching program — Computational model relevant to the group branching program application.
  • Chinese remainder theorem — Used in modulus reduction step.
  • Fourier analysis for Boolean functions — Background for the Fourier growth bound.

149 words

Radar Profile

The profile shows a balanced high performance across all dimensions, with particularly high scores in technical depth and information quality. The slightly lower (but still high) scores in quantity and reliability likely reflect the specialized nature and the succinct presentation, but overall the talk is exceptionally strong.

Reliability 9/10