Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

We show that any private-key encryption scheme that is weakly
homomorphic with respect to addition modulo 2, can be transformed
into a public-key encryption scheme. The homomorphic feature
referred to is a minimalistic one; that is, the length of a
homomorphically generated encryption should be independent of the
number of ... more >>>