CAREER: Algebraic and Combinatorial Structures In Complexity Theory

职业：复杂性理论中的代数和组合结构

• 批准号: 1350481
• 负责人: Shachar Lovett
• 金额: $ 50万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-02-01 至 2019-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1350481&HistoricalAwards=false
• 关键词: CAREER; Algebraic; Combinatorial; Structures; Complexity

The influence that computers have on our daily lives is enabled by efficient algorithms. A vast body of research is devoted to algorithmic design, but we still cannot solve most of the important computational problems that arise in science and engineering. This is captured by the famous P vs NP problem in computational complexity, which is the most important mathematical problem of our times.In this project, the PI describes a plan to address some of the challenges of computational complexity by exploring deep mathematical questions about algebraic and combinatorial structures and their applications to fundamental problems in computer science. Specifically, the focus of this proposal is on two mathematical themes: (1) low rank and combinatorial structure in matrices and (2) structure of low-degree polynomials. The unified view of the common mathematical framework allows us to relate techniques, results and problems between seemingly unrelated fields in computer science, such as: algorithm design, communication protocols, error correcting codes, de-randomization, and computational lower bounds. This research is also tightly related to some fundamental problems in mathematics, in particular in combinatorics and number theory.The PI plans to organize interdisciplinary workshops that will bring together researchers in complexity theory and other disciplines in order to learn and collaborate. The educational plans are integrated with the research and include undergraduate and graduate course development, experimentation with innovative instructional approaches, in particular the flipped classroom, mentoring of students, and outreach to engage pre-college students from diverse socio-economic backgrounds.

计算机对我们日常生活的影响是通过高效的算法实现的。大量研究致力于算法设计，但我们仍然无法解决科学和工程中出现的大多数重要计算问题。计算复杂性中著名的 P vs NP 问题就体现了这一点，这是我们这个时代最重要的数学问题。在这个项目中，PI 描述了一个计划，通过探索有关代数的深层数学问题来解决计算复杂性的一些挑战。和组合结构及其在计算机科学基本问题中的应用。具体来说，该提案的重点是两个数学主题：（1）矩阵中的低秩和组合结构以及（2）低次多项式的结构。通用数学框架的统一视图使我们能够将计算机科学中看似不相关的领域之间的技术、结果和问题联系起来，例如：算法设计、通信协议、纠错码、去随机化和计算下限。这项研究还与数学中的一些基本问题密切相关，特别是在组合学和数论方面。PI 计划组织跨学科研讨会，将复杂性理论和其他学科的研究人员聚集在一起，以便学习和协作。教育计划与研究相结合，包括本科生和研究生课程开发、创新教学方法（特别是翻转课堂）的实验、学生指导以及吸引来自不同社会经济背景的大学预科学生的外展活动。