CAREER: New Directions in Arithmetic Computation

点击翻译按钮获取中文摘要

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.