CAREER: Algebraic and Combinatorial Structures In Complexity Theory

University Of California-San Diego, La Jolla CA

Investigators

Abstract

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.