6 papers
On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC
Swastik Kopparty, Shubhangi Saraf
The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how t…
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…
Recovering polynomials over finite fields from noisy character values
Swastik Kopparty
Let be a polynomial over a finite field with degree , and let be the quadratic residue character. We give a polynomial time algorithm to rec…
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…
Permanental rank versus determinantal rank of random matrices over finite fields
Fatemeh Ghasemi, Gal Gross, Swastik Kopparty
This paper is motivated by basic complexity and probability questions about permanents of random matrices over finite fields, and in particular, about properties separating the per…
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 …