This paper is motivated by basic complexity and probability questions about permanents of random matrices over small finite fields, and in particular, about properties separating the permanent and the determinant.

Fix $q = p^m$ some power of an odd prime, and let $k \leq n$ both be growing. For ... more >>>

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 >>>

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 many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector
based PIRs of Yekhanin and Efremenko. Previously ... more >>>