All reports by Author Yang Li:

__
TR11-103
| 31st July 2011
__

Yang Li#### BQP and PPAD

__
TR11-025
| 19th February 2011
__

Yang Li#### Monotone Rank and Separations in Computational Complexity

Revisions: 1
,
Comments: 1

__
TR11-011
| 1st February 2011
__

Ming Lam Leung, Yang Li, Shengyu Zhang#### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

Yang Li

We initiate the study of the relationship between two complexity classes, BQP

(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,

Directed). We first give a conjecture that PPAD is contained in BQP, and show

a necessary and sufficient condition for the conjecture to hold. Then we prove

that the conjecture ...
more >>>

Yang Li

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>