A New Approach to the Sensitivity Conjecture

DOI10.1145/2688073.2688096zbMath1364.68197arXiv1511.07729OpenAlexW2006991246MaRDI QIDQ2989036

Justin Gilmer, Michal Koucký, Michael E. Saks

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.07729

zbMATH Keywords

decision treescommunication complexitysensitivity conjecturedegree of Boolean functions

Mathematics Subject Classification ID

Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (5)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Recognizing read-once functions from depth-three formulas ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

This page was built for publication: A New Approach to the Sensitivity Conjecture