AF: Small: Algebraic Tools for Coding, Complexity and Combinatorics

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

This project develops algebraic tools for applications in computational complexity, coding theory and incidence geometry. These application domains describe three areas within the fields of computer science, electrical and mathematics driven by very distinct motivations. Computational complexity aims to understand the fundamental limits of algorithms. Coding theory aims to study methods that can protect digital information from errors that inevitably creep in to every storage medium or communication channel. Incidence geometry studies combinatorial properties, such as size of dimension, of points in space that satisfy nice geometric properties. Despite the vast difference in scope, many central results in the three areas have come about by an understanding of basic algebraic properties of functions. This project aims to develop this basic understanding further to enable many more of such applications, and to bring these areas together. Some central algebraic properties that are being explored in this project include (1) highly-efficient randomized methods to test if a multivariate function is essentially a low-degree polynomial, (2) study of how symmetries of algebraic properties enable highly-efficient tests, and (3) use of higher-order derivatives in the study of incidence geometry. The project involves the mentoring and education of junior researchers (Ph.D. candidates) who intend to pursue their own careers in research, especially those interested in interdisciplinary studies within mathematics, electrical engineering and computer science. The education component of this project will develop courses and material of use in this interdisciplinary research project, and thus also help contribute to its broad impact.