12 citations · 27 across the 28 of their papers we have counts for
38 papers
Explicit Nonlinear Functions beyond the Fourier bound
Swastik Kopparty, Rishabh Kothary, Shanthanu S. Rai
We study the problem of constructing highly nonlinear vectorial maps . Concretely, we want an and an as small as possible, s…
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 reco…
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…