71 citations · 455 across the 36 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013
Efficient quantum protocols for XOR functions
Shengyu Zhang
We show that for any Boolean function f on {0,1}^n, the bounded-error quantum communication complexity of XOR functions satisfies that $Q_ε(f\circ \oplus) = O(2^d (…
cs.CC2013★ 6 cited
Fourier sparsity, spectral norm, and the Log-rank conjecture
Hing Yin Tsang, Chung Hoi Wong, Ning Xie +1
We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fair…
cs.DS2013★ 3 cited
Solving Linear Programming with Constraints Unknown
Xiaohui Bei, Ning Chen, Shengyu Zhang
What is the value of input information in solving linear programming? The celebrated ellipsoid algorithm tells us that the full information of input constraints is not necessary; t…