CAREER: Structure and Analysis of Low Degree Polynomials

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The primary goal of complexity theory is to design fast algorithms for solving various computational problems and to understand when such algorithms will not exist. In order to do this, a number of sophisticated mathematical tools are often required. One of the more prominent tools used in this way are polynomials. Polynomials are both varied enough to express or approximate a number of objects of interest, and yet are also simple enough that properties of them can be easily understood. Thus, relating properties of the objects in question to properties of polynomials is a well-known technique that shows up in many areas of computer science. Unfortunately, our understanding of these fundamental objects is far from complete. In fact, there are a number of problems for which our lack of understanding can be seen as a bottleneck for proving further results about problems of interest. This project will focus on attempts to remedy this gap. In particular, the PI plans to follow up on several recent advances in understanding of this area and to attempt to leverage any new results to gain insight into other important questions within computer science. In addition to leading to new algorithms of practical import, the research promises to have potential impacts in other fields such as probability theory and algebraic geometry. More specifically, the PI intends to improve upon existing tools for understanding low degree polynomials in many variables. Of particular interest would be work relating to results on the distribution of the values of such a polynomial on random inputs, with particular focus on recent structural results that allow one to decompose arbitrary polynomials in terms of better behaved ones. Having attained such results, the project will continue by making use of these improvements in order to make progress on other important problems in theoretical computer science. In particular, there are a number of specific problems in the areas of explicit pseudorandom generators, machine learning, and circuit complexity for which such technical improvements show promise for providing substantial new results. In addition to the research component of this project, the PI intends to help provide new educational opportunities particularly with regard to learning mathematical problem solving skills which are a key component of mathematics and computer science research.