[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR

Shengyu Zhang
Chinese University of Hong Kong
www.cse.cuhk.edu.hk/~syzhang/

Tuesday, May 13, 2014
3:00 pm
Ryerson 251


Title: Fourier sparsity, spectral norm, and the Log-rank conjecture

Abstract: We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show 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. 

Refreshments will be served prior to the talk in Ryerson 255 at 2:30 p.m.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140513/777b1ca0/attachment.htm