CAREER: New Directions in Arithmetic Computation

职业：算术计算的新方向

• 批准号: 1350572
• 负责人: Shubhangi Saraf
• 金额: $ 49.44万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-02-01 至 2020-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1350572&HistoricalAwards=false
• 关键词: CAREER; New; Directions; 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.

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