CAREER: Understanding Polynomial Structure Analytically and Algorithmically

点击翻译按钮获取中文摘要

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.