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.

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