The overarching goal of the project is to understand the power and limitations of algebraic computation, and the main foci are the problems of showing lower bounds for arithmetic circuits and polynomial identity testing. These problems have played a central role in various areas of Theoretical Computer Science, and they form the algebraic analog of the P vs NP question. This project will develop several new approaches and techniques for advancing our understanding of both questions. Algebraic techniques have also seen several unexpected connections in pseudorandomness and coding theory. The potential of these methods is still far from understood. In this project the PI will develop these methods, in particular the method of multiplicities and partial derivatives, to give more powerful lower bounds, and new strengthened constructions of pseudorandom objects.
The research direction proposed in this project brings together ideas and tools from a broad array of disciplines and witnesses a lot of fruitful interaction between mathematics, computational complexity, as well as practical applications to information storage and retrieval. The PI will disseminate research findings by giving lectures, talks and developing new courses and making the material available online. The PI will be actively involved in mentoring young researchers, including high school students and minorities, who want to pursue research in Theoretical Computer Science. The PI will also organize a specialized workshop for women in Theoretical Computer Science, which will bring together women researchers from all over the world.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
Mrinal Kumar, Shubhangi Saraf. "The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In," SIAM J. Computing, 2015.
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka. "Equivalence of Polynomial Identity Testing and Polynomial Factorization," Computational Complexity, 2015.
Please report errors in award information by writing to: email@example.com.