Abstract
The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}\), block sensitivity of f is polynomially related to sensitivity of f (denoted by \(\mathsf {s}(f)\)). From the complexity theory side, the Xor Log-Rank Conjecture states that for any Boolean function, \(f:\{0,1\}^n\rightarrow \{0,1\}\) the communication complexity of a related function \(f^{\oplus }:\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}\), (defined as \(f^{\oplus }(x,y) = f(x \oplus y)\)) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f, denoted by \(\mathsf {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 \(\mathsf {alt}(f)\)) for all Boolean functions f by polynomial in \(\mathsf {s}(f)\) and logarithm of \(\mathsf {sparsity}(f)\), respectively. In this context, we show the following results:
-
We show that there exists a family of Boolean functions for which \(\mathsf {alt}(f)\) is at least exponential in \(\mathsf {s}(f)\) and \(\mathsf {alt}(f)\) is at least exponential in \(\log \mathsf {sparsity}(f)\). Enroute to the proof, we also show an exponential gap between \(\mathsf {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 \(\mathsf {alt}(f)\) and \(\log \mathsf {sparsity}(f)\), the Xor Log-Rank Conjecture is true for functions with the alternation upper bounded by \({\mathsf {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, \(\mathsf {deg}(f) \le \mathsf {alt}(f)\mathsf {deg_{{\mathbb {F}}_2}}(f)^2\) where \(\mathsf {deg}(f)\) and \(\mathsf {deg_{{\mathbb {F}}_2}}(f)\) are the degrees of f over \({\mathbb {R}}\) and \({\mathbb {F}}_2\). We give two further applications of this bound: (1) We show that Boolean functions with bounded alternation have high sparsity (\(\varOmega (\sqrt{\mathsf {deg}(f)})\)), thus partially answering a question of Kulkarni and Santha (2013). (2) We observe that the above relation improves the upper bound for influence to \(\mathsf {deg_{{\mathbb {F}}_2}}(f)^2 \cdot \mathsf {alt}(f)\) improving Guo and Komargodski (2017).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
When f is monotone, it is known that \(\textsf {DT}(f) \le \mathsf {s}(f)^2\) and \(\mathsf {s}(f) \le \mathsf {deg_{{\mathbb {F}}_2}}(f)\) (Corollary 5 and Proposition 4 of [5]). Proposition 4 of [5] though states that \(\mathsf {s}(f) \le \mathsf {deg}(f)\) for any monotone f, the argument is valid for \(\mathsf {deg_{{\mathbb {F}}_2}}(f)\) also. Since, \(\mathsf {deg}(f) \le \textsf {DT}(f)\) (cf. [5]), \(\mathsf {deg}(f) \le \mathsf {deg_{{\mathbb {F}}_2}}(f)^2\).
- 2.
References
Ambainis, A., Prūsis, K., Vihrovs, J.: Sensitivity versus certificate complexity of Boolean functions. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 16–28. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34171-2_2
Bafna, M., Lokam, S.V., Tavenas, S., Velingker, A.: On the sensitivity conjecture for read-\(k\) formulas. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Kraków, Poland, pp. 16:1–16:14 (2016)
Bernasconi, A., Codenotti, B.: Spectral analysis of Boolean functions as a graph eigenvalue problem. IEEE Trans. Comput. 48(3), 345–351 (1999)
Blais, E., Canonne, C.L., Oliveira, I.C., Servedio, R.A., Tan, L.-Y.: Learning circuits with few negations. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, 24–26 August 2015, Princeton, NJ, USA, pp. 512–527 (2015)
Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21–43 (2002)
Karthik, C.S., Tavenas, S.: On the sensitivity conjecture for disjunctive normal forms. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, 13–15 December 2016, Chennai, India, pp. 15:1–15:15 (2016)
Chakraborty, S.: On the sensitivity of cyclically-invariant Boolean functions. Discrete Math. Theor. Comput. Sci. 13(4), 51–60 (2011)
Cook, S., Dwork, C., Reischuk, R.: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. 15(1), 87–97 (1986)
Gilmer, J., Koucký, M., Saks, M.E.: A new approach to the sensitivity conjecture. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, pp. 247–254. ACM, New York (2015)
Gopalan, P., Servedio, R.A., Wigderson, A.: Degree and sensitivity: tails of two distributions. In: 31st Conference on Computational Complexity, CCC 2016, Tokyo, Japan, pp. 13:1–13:23 (2016)
Guo, S., Komargodski, I.: Negation-limited formulas. Theor. Comput. Sci. 660, 75–85 (2017)
Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theor. Comput. Libr. Grad. Surv. 4, 1–27 (2011)
Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Springer, Heidelberg (2012)
Kenyon, C., Kutin, S.: Sensitivity, block sensitivity, and \(\ell \)-block sensitivity of Boolean functions. Inf. Comput. 189(1), 43–53 (2004)
Kulkarni, R., Santha, M.: Query complexity of matroids. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 300–311. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38233-8_25
Lin, C., Zhang, S.: Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), vol. 80, pp. 51:1–51:13, Dagstuhl, Germany (2017)
Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform, and learnability. J. ACM 40(3), 607–620 (1993)
Markov, A.A.: On the inversion complexity of a system of functions. J. ACM 5(4), 331–334 (1958)
Montanaro, A., Osborne, T.: On the communication complexity of XOR functions. CoRR abs/0909.3392 (2009)
Nisan, N.: CREW PRAMs and decision trees. SIAM J. Comput. 20(6), 999–1007 (1991)
Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 462–467. ACM, New York (1992)
O’Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, New York (2014)
Simon, H.-U.: A tight \(\omega \)(loglog n)-bound on the time for parallel Ram’s to compute nondegenerated boolean functions. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol. 158, pp. 439–444. Springer, Heidelberg (1983). https://doi.org/10.1007/3-540-12689-9_124
Tal, A.: Properties and applications of Boolean function composition. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 441–454. ACM, New York (2013)
Tsang, H.Y., Wong, C.H., **e, N., Zhang, S.: Fourier sparsity, spectral norm, and the log-rank conjecture. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October 2013, Berkeley, CA, USA, pp. 658–667 (2013)
Turán, G.: The critical complexity of graph properties. Inf. Process. Lett. 18(3), 151–153 (1984)
Zhang, Z., Shi, Y.: Communication complexities of symmetric XOR functions. Quantum Inf. Comput. 9(3), 255–263 (2009)
Zhang, Z., Shi, Y.: On the parity complexity measures of Boolean functions. Theor. Comput. Sci. 411(26–28), 2612–2618 (2010)
Acknowledgments
The authors would like to thank the anonymous reviewers for constructive comments which improved the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Dinesh, K., Sarma, J. (2018). Alternation, Sparsity and Sensitivity: Combinatorial Bounds and Exponential Gaps. In: Panda, B., Goswami, P. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2018. Lecture Notes in Computer Science(), vol 10743. Springer, Cham. https://doi.org/10.1007/978-3-319-74180-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-74180-2_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74179-6
Online ISBN: 978-3-319-74180-2
eBook Packages: Computer ScienceComputer Science (R0)