Simple pseudorandom constructions in algebra @SimonsInstitute
Simple pseudorandom constructions in algebra  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 3 days ago
Robert Andrews (Simon Fraser University)
https://simons.berkeley.edu/talks/robert-andrews-simon-fraser-university-2026-10-28
Derandomization

Polynomial identity testing (PIT) is a central problem in theoretical computer science with numerous algorithmic applications, including applications to problems with no obvious algebraic character. Known polynomial-time algorithms for PIT crucially rely on the use of randomness. Designing a deterministic polynomial-time algorithm for PIT is a major goal of algebraic complexity theory.

Often, algorithms for PIT are obtained by constructing pseudorandom objects known as hitting set generators. Recently, there has been interest in constructing such hitting set generators in a “cryptographic” regime of parameters, where the complexity of the generator is very small compared to the class of algebraic circuits it fools.

In this talk, I will describe a new construction of a generator where each output can be computed by a formula of constant size and the generator itself fools algebraic circuits of polynomial size and constant depth. Under strong (but reasonable) hardness assumptions, this generator also fools polynomial-size algebraic branching programs.
Simple pseudorandom constructions in algebraThe unreasonable effectiveness of the convexity assumption in high dimensions
Simons Institute for the Theory of Computing |

Simple pseudorandom constructions in algebra

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER