3 papers
cs.IT2025
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…
cs.CC2025
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…
cs.CC2024
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…