Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$74,000.00

Locality in Error-Correcting Codes

EF 2022-23

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-04658
Name nom
Kopparty, Swastik
Department département
Mathematics (St. George Campus) - Mathematics (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1
Partie
1
Nb partie
5
Application title
Locality in Error-Correcting Codes
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.