Paper 2025/2289

Fourier Sparsity of Delta Functions and Matching Vector PIRs

Abstract

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 Retrieval (PIR) schemes. For integers $m,r$, define a delta function on $\{0,1\}^r \subseteq \mathbb{Z}_m^r$ to be a function $f: \mathbb{Z}_m^r \to \mathbb C$ if $f(0) = 1$ and $f(x) = 0$ for all nonzero Boolean $x$. The basic question that we study is how small can the Fourier sparsity of a delta function be; namely, how sparse can such an $f$ be in the Fourier basis? In addition to being intrinsically interesting and natural, such questions arise naturally while studying "$S$-decoding polynomials" for the known matching vector families. Finding $S$-decoding polynomials of reduced sparsity -- which corresponds to finding delta functions with low Fourier sparsity -- would improve the current best PIR schemes. We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improvements to the Matching Vector PIR schemes simply by finding better $S$-decoding polynomials. In particular, there are no $S$-decoding polynomials which can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication for constantly many servers. Many interesting questions remain open.