Skip to main content
Upcoming Events:

Seminar: Zeyu Guo

Date & Time:
   Add All to Calendar

Hardness vs. Randomness in Algebraic Complexity Theory

Overview

Abstract

Randomness is a powerful tool in the design of algorithms. But is it really necessary? The hardness vs. randomness paradigm in complexity theory provides a way of converting computationally hard problems to small sets of "pseudorandom" strings, which can be used to deterministically simulate randomized algorithms with a small overhead.

Hardness vs. randomness has also been intensively studied in algebraic complexity theory, an area devoted to understanding the computational complexity of polynomials in algebraic models. In this talk, I will describe our new construction of "hitting-set generators" in the algebraic hardness vs. randomness paradigm, which converts computationally hard polynomials to efficient deterministic algorithms solving the polynomial identity testing (PIT) problem. Its analysis is based on an iterative method analogous to Newton's method in numerical analysis. Our result also implies that beating the trivial PIT algorithm in the constant-variate regime is as difficult as solving the general PIT problem in deterministic polynomial time.

Bio

Zeyu Guo is a postdoctoral researcher at the University of Haifa, Israel working with Prof. Noga Ron-Zewi on pseudorandomness and error-correcting codes. Prior to that, he was a postdoc at the Indian Institute of Technology Kanpur working with Prof. Nitin Saxena. Zeyu received his Ph.D. degree in Computer Science from the California Institute of Technology in 2017 with a dissertation on "P-schemes and deterministic polynomial factoring over finite fields". His research interests include pseudorandomness, coding theory, algebraic complexity theory, and algebraic algorithms.