We study the problem of non-interactive correlation distillation (NICD). Suppose Alice and Bob each has a string, denoted by $A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$, respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is independently drawn from a distribution $\noise$, known as the ``noise mode''. Alice and Bob wish to ``distill'' the correlation ... more >>>

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>

We introduce a ``Statistical Query Sampling'' model, in which the goal of an algorithm is to produce an element in a hidden set $S\subseteq\bit^n$ with reasonable probability. The algorithm gains information about $S$ through oracle calls (statistical queries), where the algorithm submits a query function $g(\cdot)$ and receives an approximation ... more >>>

We prove two lower bounds on the Statistical Query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension $d$, a running time of $\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is defined to be the maximum number ... more >>>

In this paper, we study the problem of using statistical query (SQ) to learn highly correlated boolean functions, namely, a class of functions where any pair agree on significantly more than a fraction 1/2 of the inputs. We give a limit on how well one can approximate all the functions ... more >>>

Informally, an obfuscator O is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic ... more >>>

In this paper, we address the problem of evaluating the Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over the set of natural numbers. The problem is a natural extension to the integer expression by Stockmeyer and Mayer, and is also studied by Mckenzie, Vollmer and Wagner in their ``Polynomial ... more >>>