Alternation, sparsity and sensitivity: Combinatorial bounds and exponential gaps

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function (Formula presented), 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, (Formula presented) the communication complexity of a related function (Formula presented), (defined as (Formula presented)) 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 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). Enroute 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 logsparsity(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, (Formula presented) where deg(f) and (Formula presented) are the degrees of f over R and F2. We give two further applications of this bound: (1) We show that Boolean functions with bounded alternation have high sparsity (Formula presented), thus partially answering a question of Kulkarni and Santha (2013). (2) We observe that the above relation improves the upper bound for influence to (Formula presented) improving Guo and Komargodski (2017).