In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for computing ... more >>>

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>