All reports by Author Ke Yang:

__
TR03-085
| 28th November 2003
__

Ke Yang#### On the (Im)possibility of Non-interactive Correlation Distillation

__
TR03-082
| 22nd November 2003
__

Andris Ambainis, Ke Yang#### Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

__
TR03-014
| 28th February 2003
__

Avrim Blum, Ke Yang#### On Statistical Query Sampling and NMR Quantum Computing

__
TR02-060
| 15th July 2002
__

Ke Yang#### New Lower Bounds for Statistical Query Learning

__
TR01-098
| 19th November 2001
__

Ke Yang#### On Learning Correlated Boolean Functions Using Statistical Query

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR00-012
| 14th February 2000
__

Ke Yang#### Integer Circuit Evaluation is PSPACE-complete

Ke Yang

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 >>>

Andris Ambainis, Ke Yang

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 >>>

Avrim Blum, Ke Yang

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 ...
more >>>

Ke Yang

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 >>>

Ke Yang

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 ...
more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Ke Yang

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 ...
more >>>