4 papers · 1 filter
Algebraic Expander Codes
Swastik Kopparty, Itzhak Tamo
Expander (Tanner) codes combine sparse graphs with local constraints, enabling linear-time decoding and asymptotically good distance--rate tradeoffs. A standard constraint-counting…
Fourier Sparsity of Delta Functions and Matching Vector PIRs
Fatemeh Ghasemi, Swastik Kopparty
In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Re…
High Rate Multivariate Polynomial Evaluation Codes
Swastik Kopparty, Mrinal Kumar, Harry Sha
The classical Reed-Muller codes over a finite field are based on evaluations of -variate polynomials of degree at most over a product set , for some …
Error-Correcting Graph Codes
Swastik Kopparty, Aditya Potukuchi, Harry Sha
In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance is a family of graphs on a common vertex set of size , such that if…