We introduce the entangled quantum polynomial hierarchy QEPH as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove QEPH collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. ... more >>>

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
That is, given n d-bit memory locations, we present an information-theoretically secure protocol which requires o(d \cdot \log(n)) bits of communication per access (when d = \Omega(\log^2(n)).

This comes as a surprise, ... more >>>

An n-variate polynomial g of degree d is a (n,d,t) design polynomial if the degree of the gcd of every pair of monomials of g is at most t-1. The power symmetric polynomial \mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i and the sum-product polynomial \mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j} are instances of design polynomials ... more >>>