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…