This concise, accessible text provides a thorough introduction to quantum computing-an
exciting emergent field at the interface of the computer, engineering, mathematical and …

A thorough exposition of quantum computing and the underlying concepts of quantum
physics, with explanations of the relevant mathematics and numerous examples. The …

Property testing is concerned with the design of super-fast algorithms for the structural
analysis of large quantities of data. The aim is to unveil global features of the data, such as …

I study the class of problems efficiently solvable by a quantum computer, given the ability to
'postselect'on the outcomes of measurements. I prove that this class coincides with a …

We continue the study of the trade-off between the length of PCP sand their query
complexity, establishing the following main results (which refer to proofs of satisfiability of …

Private information retrieval (PIR) protocols allow a user to retrieve a data item from a
database while hiding the identity of the item being retrieved. Specifically, in information …

Alice wants to query a database but she does not want the database to learn what she is
querying. She can ask for the entire database. Can she get her query answered with less …

Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input
message by making a constant number of queries to a codeword, even if a constant fraction …

A q-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit
codeword C (x), such that one can probabilistically recover any bit xi of the message by …

We show tight upper and lower bounds for time-space trade-offs for the c-approximate Near
Neighbor Search problem. For the d-dimensional Euclidean space and n-point datasets, we …