CAREER: Algebraic Pseudorandomness in Complexity and Coding Theory

Most computers generate random-looking numbers without using any randomness at all; instead, the numbers are generated by a mathematical sequence that appears random. This might not be random enough for every application. Pseudorandomness, a key idea in theoretical computer science, involves constructing mathematical objects that exhibit random-like behavior while being created in a predictable way.

These objects are essential for solving problems where true randomness is computationally costly or impractical to generate. The project addresses challenges such as developing efficient algorithms to determine whether complex mathematical expressions simplify to zero, a critical question in areas like algorithm design and circuit complexity. It also explores connections to error-correcting codes, which ensure reliable communication and data storage by correcting transmission errors.

By advancing knowledge in these areas, the project contributes to foundational methods in computation and communication systems while supporting the national interest through fundamental research. The project also includes educational initiatives to create resources and courses that inspire the next generation of scholars in mathematics and computer science.

The work spans computational complexity and coding theory, unified under the theme of algebraic pseudorandomness. In complexity theory, the project focuses on deterministic methods for polynomial identity testing in special classes of arithmetic circuits, addressing a central problem in derandomization. It also applies algebraic geometry to study structural properties of algebraic varieties that arise in computational problems, offering new perspectives in complexity theory.

On the coding theory side, the research examines the combinatorial and algebraic properties of error-correcting codes, particularly list-decodable and list-recoverable codes, with the goal of developing more efficient constructions and improving their theoretical guarantees. By tackling these challenges, the project advances fundamental questions in pseudorandomness and contributes novel insights to the fields of complexity theory and coding theory.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.