We 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 M f for such functions is exactly the Fourier sparsity of f . Let d = deg 2 (f ) be the F2-degree of f and D CC (f • ⊕) stand for the deterministic communication complexity for f (x ⊕ y). We show that the Log-rank conjecture holds for XOR functions with constant F2-degree. 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(M f ). The above bounds are obtained from different analysis for the number of parity queries required to reduce f 's F2-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 polylog f 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 .
A recent work of Tsang et al REF established similar bounds to Theorem 1.1 for the special case of functions of the form f (x, y) = F (x ⊕ y).
Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science