Grant: Discovery Grants Program - Individual
University of Toronto
$74,000.00
Locality in Error-Correcting Codes
FY 2024-25
Summary
This project investigates the main problems on the existence, construction, algorithms and limitations for
*local* error-correcting codes, as well as their implications across theoretical computer science.
Error-correcting codes give a way of formatting data so as to make it robust to errors.
Local error-correcting codes are error-correcting codes with rich local structure,
enabling super-fast detection and correction of errors. Apart from their natural
applications to data storage and communication, they form the combinatorial
core of Probabilistically Checkable Proofs for NP, and they underlie a number of breakthroughs in
complexity theory, cryptography and pseudorandomness over the past three decades.
This project is motivated by number of recent advances by the PI, significantly deepening
our understanding of local error-correcting codes, and exposing a wide range of new questions and possibilities.
Some of these advances include the construction of new high rate error-correcting codes allowing, for the first time,
subpolynomial-time error-correction and error-detection, and the first constructions of Probabilistically Checkable Proofs of constant
rate, checkable in sublinear time. The algebraic and probabalistic tools developed along the way enabled
other advances by the PI in related fields, such as a new FFT-like algorithm based on elliptic curves,
leading to the asymptotically fastest univariate polynomial interpolation algorithm for a general finite field,
and the first list-decodable and locally list-decodable codes with constant list size and constant alphabet size.
The main goal of this project is to understand the fundamental tradeoffs between locality, redundancy
of encoding and robustness to errors that local error-correcting codes have. The tantalizing message of the
previously mentioned results is that, as far as we know, locality can come for *free*; this project aims to
get to the bottom of this, potentially resolving central questions about codes and Probabilistically Checkable Proofs.
In addition, the project will investigate implications of this newly found understanding of local codes for other areas
across theoretical computer science. Finally, this project will develop algebraic, probabilistic and algorithmic methods for
reasoning about locality and information. Along the way, this project will explore other closely related directions, such as
the development of fast algebraic algorithms and applications of coding to pseudorandomness and complexity theory.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-04658
Name nom
Kopparty, Swastik
Department département
Mathematics
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
74000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Locality in Error-Correcting Codes
Keywords
error-correcting codes; local decoding; polynomials; probabilistically checkable proofs; sublinear time algorithms; complexity theory
Application summary
This project investigates the main problems on the existence, construction, algorithms and limitations for
*local* error-correcting codes, as well as their implications across theoretical computer science.
Error-correcting codes give a way of formatting data so as to make it robust to errors.
Local error-correcting codes are error-correcting codes with rich local structure,
enabling super-fast detection and correction of errors. Apart from their natural
applications to data storage and communication, they form the combinatorial
core of Probabilistically Checkable Proofs for NP, and they underlie a number of breakthroughs in
complexity theory, cryptography and pseudorandomness over the past three decades.
This project is motivated by number of recent advances by the PI, significantly deepening
our understanding of local error-correcting codes, and exposing a wide range of new questions and possibilities.
Some of these advances include the construction of new high rate error-correcting codes allowing, for the first time,
subpolynomial-time error-correction and error-detection, and the first constructions of Probabilistically Checkable Proofs of constant
rate, checkable in sublinear time. The algebraic and probabalistic tools developed along the way enabled
other advances by the PI in related fields, such as a new FFT-like algorithm based on elliptic curves,
leading to the asymptotically fastest univariate polynomial interpolation algorithm for a general finite field,
and the first list-decodable and locally list-decodable codes with constant list size and constant alphabet size.
The main goal of this project is to understand the fundamental tradeoffs between locality, redundancy
of encoding and robustness to errors that local error-correcting codes have. The tantalizing message of the
previously mentioned results is that, as far as we know, locality can come for *free*; this project aims to
get to the bottom of this, potentially resolving central questions about codes and Probabilistically Checkable Proofs.
In addition, the project will investigate implications of this newly found understanding of local codes for other areas
across theoretical computer science. Finally, this project will develop algebraic, probabilistic and algorithmic methods for
reasoning about locality and information. Along the way, this project will explore other closely related directions, such as
the development of fast algebraic algorithms and applications of coding to pseudorandomness and complexity theory.