CAREER: Understanding Polynomial Structure Analytically and Algorithmically

开发新的分析工具和证明技术将从根本上推动计算机科学的发展。这个项目的目的是以统一的方式探索在理论计算机科学和数学的几个不同领域中使用的技术。其中一个发展涉及到对低次多项式的研究。本研究将解决两个主要考虑的问题：-理解与有限域上的低次多项式有微小但重要相关性的函数的解析结构。-了解低次多项式在实数上的表达能力，以捕获几个组合事实的证明。前者导致了许多问题，涉及算术组合、编码理论、学习理论、近似硬度和傅立叶分析等领域。其中一些问题扩展了编码理论中的列表解码概念，也是开发高阶傅立叶分析理论的算法版本的关键，该理论最近发展用于研究算术组合中的问题。后一种考虑将加强我们对组合优化和证明复杂性技术的理解。在这些问题上的进展将有助于利用线性和半定规划设计新的近似算法。该项目的一部分内容还包括设计两门新课程，分别在丰田技术学院和芝加哥大学开设。PI还计划收集简短的“研究摘要”，概述不同理论领域的一些令人兴奋的问题，并将其提供给高级高中生和本科生。

Developing new analytic tools and proof techniques will advance computer science in a fundamental way. The aim of this project is to explore techniques used in several different areas of theoretical computer science and mathematics in a unified way. One such development involves the study of low-degree polynomials. This research will address problems arising from two main considerations:- Understanding the analytical structure of functions which have a small but significant correlation with a low-degree polynomial over a finite field.- Understanding the expressive power of low-degree polynomials over reals for capturing proofs of several combinatorial facts.The former leads to many questions spanning the areas of arithmetic combinatorics, coding theory, learning theory, hardness of approximation and Fourier analysis. Some of these questions extend the notions of list-decoding in coding theory and are also key to developing an algorithmic version of the theory of higher-order Fourier analysis, developed recently to study questions in arithmetic combinatorics. The latter consideration will strengthen our understanding of techniques from combinatorial optimizations and proof complexity. Progress on these questions will shed light on the design of new approximation algorithms using linear and semidefinite programs.Part of this project also includes designing two new courses, to be offered at Toyota Technical Institute and the University of Chicago. The PI also plans to collect short "research summaries" to outline some of the exciting questions in different areas of theory, and make them accessible to advanced high-school and undergraduate students.