Fourier sparsity, spectral norm, and the Log-rank conjecture
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractWe study Boolean functions with sparse Fourier spectrum or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x y) - A fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix Mf for such functions is exactly the Fourier sparsity of f. Let d = deg2(f) be the 2-degree of f and DCC(f.) stand for the deterministic communication complexity for f(x y). We show that 1) DCC(f.) = O(2d2/2 logd-2 ̂ f1). In particular, the Log-rank conjecture holds for XOR functions with constant 2-degree. 2) DCC(f.) = O(d∥̂ f∥1) = ̃O(√rank(Mf )). This improves the (trivial) linear bound by nearly a quadratic factor. We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that the communication cost of our protocol is at most log O(1) rank(Mf ). The above bounds are obtained from different analysis for the number of parity queries required to reduce f's 2-degree. Our bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity. Along the way we also prove several structural results about Boolean functions with small Fourier sparsity ∥ f̂̂0 or spectral norm ̂ f̂ ̂ 1, which could be of independent interest. For functions f with constant F2-degree, we show that: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with ±-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; and 3) f depends only on polylogf̂1 linear functions of input variables. For functions f with small spectral norm, we show that: 1) there is an affine subspace of co-dimension O(∥ f̂∥1) on which f(x) is a constant, and 2) there is a parity decision tree of depth O(∥ f̂1 log f̂∥ 0) for computing f. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.
All Author(s) ListTsang H.Y., Wong C.H., Xie N., Zhang S.
Name of Conference2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Start Date of Conference27/10/2013
End Date of Conference29/10/2013
Place of ConferenceBerkeley, CA
Country/Region of ConferenceUnited States of America
Detailed descriptionTo ORKTS: The authors are listed in alphabetical order as a convention of the scientific community of theoretical computer science.
I presented the p
Pages658 - 667
LanguagesEnglish-United Kingdom
KeywordsFourier analysis, Fourier sparsity, Log-rank conjecture, Low-degree polynomials

Last updated on 2020-14-10 at 03:42