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 {\em delta function} on $\{0,1\}^r \subseteq \mathbb Z_m^r$ to be a function $f: ... more >>>

We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between $N$ and $2N$), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem ... more >>>

Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of $\mathrm{NP}$ is a central research direction. A longstanding open problem in this area is to establish the $\mathrm{NP}$-hardness of $\mathrm{MINKT}$ [Ko91], the problem of ... more >>>