skip to main content
Caltech

CMI Seminar

Tuesday, October 2, 2018
4:00pm to 5:00pm
Add to Cal
Annenberg 314
Algebraic Complexity Theory: Lower bounds and Derandomization (1st of 2 parts)
Ben Lee Volk, CMI Postdoctoral Scholar, CMS, Caltech,

    Algebraic Complexity theory is a subfield of complexity theory, studying computational problems of algebraic flavor such as multiplying matrices, computing the determinant, and more generally, computing polynomials over a field, where the complexity is measured by the number of algebraic operations needed to compute it.
    Two basic open problems in the area are (1) proving superpolynomial circuit lower bounds for explicit polynomials (which is the algebraic analog to the P vs. NP problem), and (2) designing deterministic efficient algorithms for the Polynomial Identity Testing problem, that asks to determine, given a circuit computing a polynomial, whether it computes the zero polynomial. Studying these questions often leads to beautiful mathematical questions of combinatorial, algebraic and geometric nature.
    In this talk, we will discuss several old and new results in the area, explore the mysterious, bidirectional and intricate connections between the two problems above, and give some open problems.

For more information, please contact Linda Taddeo by phone at 626-395-6704 or by email at [email protected] or visit Mathematics of Information Seminar - Upcoming Events.