Skip to content Skip to navigation

CAREER: Error-Correcting Codes, Complexity Theory and Pseudorandomness

Principal Investigator: 
Grant Agency: 
NSF
Grant Duration: 
12/03/2012 to 01/31/2018
Amount: 
$408,684.00
Abstract: 

NSF Link

ABSTRACT

The classical theory of error-correcting codes by Shannon and Hamming has developed into a flourishing subject, and has been hugely influential in the design of communication and storage systems. However, the more modern aspects of error-correcting codes, including those relevant to complexity theory and pseudorandomness, have lagged behind, and many challenges and problems are not well understood. This project aims to remedy this situation by systematically exploring what can be achieved in the realm of local-decoding, local-testing, list-decoding and local list-decoding, and by exploring the implications of this in complexity theory and pseudorandomness. 

This project proposes to investigate new constructions of error-correcting codes supporting sublinear-time error-detection, sublinear-time error-correction and efficient list-decoding, as well as their applications in the areas of computational complexity theory and pseudorandomness. The project builds upon several recent advances made by the PI, such as the construction of new high rate error-correcting codes allowing, for the first time, sublinear-time error-correction.

The educational component of this project will involve the mentoring and education of junior researchers who intend to pursue a career in research, as well as the development and dissemination of new course materials and broadly accessible presentations of the results of this research.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval). 

Some links on this page may take you to non-federal websites. Their policies may differ from this site. 

Swastik Kopparty. "Some remarks on multiplicity codes," AMS Contemporary Mathematics, 2014.

Swastik Kopparty, Qiang Wang. "Roots and coefficients of polynomials over finite fields," Finite Fields and Applications, 2014.

Ross Berkowitz, Swastik Kopparty. "Robust Positioning Patterns," SODA, 2016.

Swastik Kopparty. "List Decoding Multiplicity Codes," Theory of Computing, 2015.

Amey Bhangale,Swastik Kopparty, Sushant Sachdeva. "Simultaneous Approximation of Constraint Satisfaction Problems," ICALP, 2015.

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka. "Equivalence of Polynomial Factorization and Polynomial Identity Testing," Computational Complexity, 2015.
 

 

 

 

Please report errors in award information by writing to: awardsearch@nsf.gov.