演讲人：
Prof. Shengyu Zhang CUHK
时间： 2014-03-11 10:00-2014-03-11 12:00
地点：FIT 1-222
内容：
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 fairly large class of functions including well-studied ones such as Equality and Hamming Distance. The rank of the communication matrix M_f for such functions is exactly the Fourier sparsity of f. Let d be the F2-degree of f and D(f) stand for the deterministic communication complexity for f(x\oplus y). We show that 1. D(f) = O(2^{d^2/2} log^{d-2} ||\hat f||_1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2. D(f) = O(d ||\hat f||_1) = O(\sqrt{rank(M_f)}\logrank(M_f)). We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that its communication cost is already\log^{O(1)}rank(M_f). The above bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity (up to a factor of 2).
Along the way we also show several structural results about Boolean functions with small F2-degree or small spectral norm, which could be of independent interest. For functions f with constant F2-degree: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with \pm-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; 3) f depends only on polylog||\hat f||_1 linear functions of input variables. For functions f with small spectral norm: 1) there is an affine subspace with co-dimension O(||\hat f||_1) on which f is a constant; 2) there is a parity decision tree with depth O(||\hat f||_1 log ||\hat f||_0).
Joint work with Tsang, Wong and Xie. Paper presented at FOCS'13.
个人简介:
Shengyu Zhang received his B.S. in Mathematics at Fudan University in 1999, his M.S. in Computer Science at Tsinghua University in 2002 (under the superposition of Prof. Mingsheng Ying), and his Ph.D. in Computer Science at Princeton University in 2006 (under the superposition of Prof. Andrew Yao). After working in NEC Laboratories America for a summer, and in California Institute of Technology for two years as a postdoc, he joined The Chinese University of Hong Kong as an assistant professor in Department of Computer Science and Engineering. His research interest focuses on algorithm designs and computational complexity in a variety of classical and quantum settings.
