X
Alternation, sparsity and sensitivity: Bounds and exponential gaps
Krishnamoorthy Dinesh,
Published in Elsevier B.V.
2019
Volume: 771

Pages: 71 - 82
Abstract
The well-known SENSITIVITY CONJECTURE regarding combinatorial complexity measures on Boolean functions states that for any Boolean function f:{0,1} n →{0,1}, block sensitivity of f is polynomially related to sensitivity of f (denoted by s(f)). From the complexity theory side, the XOR LOG-RANK CONJECTURE states that for any Boolean function, f:{0,1} n →{0,1} the communication complexity of a related function f ⊕ :{0,1} n ×{0,1} n →{0,1} (defined as f ⊕ (x,y)=f(x⊕y)) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f, denoted by sparsity(f)). Both the conjectures play a central role in the domains in which they are studied. A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures it suffices to upper bound alternation of f (denoted by alt(f)) for all Boolean functions f by polynomial in s(f) and logarithm of sparsity(f), respectively. In this context, we show the following results: • We show that there exists a family of Boolean functions for which alt(f) is at least exponential in s(f) and alt(f) is at least exponential in log⁡sparsity(f). En route to the proof, we also show an exponential gap between alt(f) and the decision tree complexity of f, which might be of independent interest. • As our main result, we show that, despite the above exponential gap between alt(f) and log⁡sparsity(f), the XOR LOG-RANK CONJECTURE is true for functions with the alternation upper bounded by poly(log⁡n). It is easy to observe that the SENSITIVITY CONJECTURE is also true for this class of functions. • The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function f, deg(f)≤alt(f)deg 2 (f)deg m (f) where deg(f), deg 2 (f) and deg m (f) are the degrees of f over R, F 2 and Z m respectively. We give three further applications of this bound: (1) We show that for Boolean functions f of constant alternation have deg 2 (f)=Ω(log⁡n). (2) Moreover, these functions also have high sparsity (exp⁡(Ω(deg(f))), thus partially answering a question of Kulkarni and Santha (2013). (3) We observe that our relation upper bounding real degree also improves the upper bound for influence to deg 2 (f) 2 ⋅alt(f) improving Guo and Komargodski (2017). © 2018 Elsevier B.V.