AF: Small: Algebraic Methods in Codes and Computation

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

This project investigates the power and limitations of algebraic computation and algebraic techniques in computer science. Arithmetic circuits are a very natural model of algebraic computation and most natural algebraic algorithms such as matrix multiplication, fast Fourier transforms, algorithms for computing the determinant, and others can be implemented via arithmetic circuits. This project will investigate the complexity of algebraic computation via the model of arithmetic circuits. In recent years algebraic techniques have shown up as an extremely powerful tool influencing all areas of computer science, including even the understanding of problems that are not inherently algebraic. Algebraic techniques have also found striking applications in combinatorics, coding theory, and pseudorandomness. Due to the profound impact of algebraic techniques and algebraic algorithms, this naturally motivates a deeper understanding of the power and limits of these methods, and this project aims to develop new tools and techniques in order to do this. One of the focuses of the project will be to harness algebraic techniques for the construction of efficient and local error-correcting codes. Mentoring and training of young researchers is an important part of the educational component of the project. Additionally, the investigator will co-organize the Women in Theory workshop in the summer of 2020, which will bring together women researchers in theoretical computer science from around the world. The two main problems that this project will explore are those of proving lower bounds for arithmetic circuits and the problem of polynomial identity testing. These are some of the most central questions in algebraic complexity theory, and this project aims to understand these via the study of bounded-depth arithmetic circuits. The project will also study two other very related problems of polynomial factoring and polynomial reconstruction. In addition, the project will use algebraic techniques to construct new families of error-correcting codes with extremely efficient encodings and with sublinear-time decoding and testing algorithms. In particular, the project will attempt to understand the optimal rate/query complexity tradeoffs in the construction of locally decodable codes and locally testable codes. This project will bring together ideas and tools from a broad array of disciplines and has the potential to have significant practical applications to information storage and retrieval. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.