Get all the updates for this publication

Articles

Alternation, sparsity and sensitivity: Bounds and exponential gapsOpen Access

Published in Elsevier B.V.

2019

Volume: 771

Pages: 71 - 82

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 logsparsity(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 logsparsity(f), the XOR LOG-RANK CONJECTURE is true for functions with the alternation upper bounded by poly(logn). 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)=Ω(logn). (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.

Preprint Version

Content may be subject to copyright.This is a green open access articleThis is a green open access article

About the journal

Journal | Data powered by TypesetTheoretical Computer Science |
---|---|

Publisher | Data powered by TypesetElsevier B.V. |

ISSN | 03043975 |

Open Access | Yes |

Concepts (12)

- Computational complexity
- Decision trees
- Fourier analysis
- Block sensitivity
- COMBINATORIAL COMPLEXITY
- Communication complexity
- Complexity theory
- FUNCTION PARAMETERS
- NON-ZERO FOURIER COEFFICIENTS
- SENSITIVITY CONJECTURE
- XOR LOG-RANK CONJECTURE
- Boolean functions