5 papers · 1 filter
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…
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…
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…
Improved PIR Schemes using Matching Vectors and Derivatives
Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely…
Small Shadow Partitions
Swastik Kopparty, Harry Sha
We study the problem of partitioning the unit cube into parts so that each -dimensional axis-parallel projection has small volume. This natural combinatorial/geome…