CAREER: Algebraic and Combinatorial Structures In Complexity Theory

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

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.