Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yang Li:

TR11-103 | 31st July 2011
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 >>>

TR11-025 | 19th February 2011
Yang Li

Monotone Rank and Separations in Computational Complexity

Revisions: 1 , Comments: 1

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.


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

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

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

ISSN 1433-8092 | Imprint