All reports by Author Shengyu Zhang:

__
TR13-010
| 4th January 2013
__

Yang Liu, Shengyu Zhang#### Quantum and randomized communication complexity of XOR functions in the SMP model

__
TR12-067
| 6th May 2012
__

Xiaohui Bei, Ning Chen, Shengyu Zhang#### On the Complexity of Trial and Error

Revisions: 1

__
TR11-033
| 8th March 2011
__

Rahul Jain, Shengyu Zhang#### The influence lower bound via query elimination

__
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

__
TR05-041
| 12th April 2005
__

Shengyu Zhang#### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Revisions: 2

Yang Liu, Shengyu Zhang

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>

Xiaohui Bei, Ning Chen, Shengyu Zhang

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

Rahul Jain, Shengyu Zhang

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies 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 >>>

Shengyu Zhang

The Local Search problem, which finds a

local minimum of a black-box function on a given graph, is of both

practical and theoretical importance to many areas in computer

science and natural sciences. In this paper, we show that for the

Boolean hypercube $\B^n$, the randomized query complexity of Local

more >>>