Please note: This seminar will take place in DC 2306 and online.
Robert Andrews, William T. Tutte Postdoctoral Fellow
David R. Cheriton School of Computer Science
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, which are analogous to the pseudorandom generators seen in boolean derandomization problems like P versus BPP. 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.
No background in algebra or pseudorandomness is necessary!
To attend this seminar in person, please go to DC 2306. You can also attend virtually on Zoom.