CAREER: New Directions in Arithmetic Computation

该项目的首要目标是了解代数计算的能力和局限性，主要焦点是证明算术电路的下界和多项式恒等式测试的问题。这些问题在理论计算机科学的各个领域中扮演着中心角色，它们形成了P与NP问题的代数模拟。这个项目将开发几种新的方法和技术来促进我们对这两个问题的理解。代数技术也在伪随机性和编码理论中看到了几个意想不到的联系。这些方法的潜力仍远未被了解。在这个项目中，PI将发展这些方法，特别是重数和偏导数方法，以给出更强大的下界，以及伪随机对象的新的强化结构。该项目提出的研究方向汇集了来自广泛学科的想法和工具，并见证了数学、计算复杂性以及信息存储和检索的实际应用之间的许多富有成效的交互作用。国际和平研究所将通过举办讲座、讲座和开发新课程并在网上提供材料来传播研究成果。PI将积极参与指导年轻的研究人员，包括高中生和少数族裔，他们希望从事理论计算机科学的研究。国际和平研究所还将为理论计算机科学领域的女性举办一次专门的讲习班，来自世界各地的女研究人员将汇聚一堂。

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.