On the resolution of the sensitivity conjecture
DOI10.1090/bull/1697zbMath1454.68107arXiv1912.05406OpenAlexW3105573633WikidataQ122936894 ScholiaQ122936894MaRDI QIDQ5123060
Siddharth Sinha, Vallabh Patil, Rohan Karthikeyan
Publication date: 25 September 2020
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.05406
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Matrix equations and identities (15A24) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Induced subgraphs of hypercubes
- Countable connected-homogeneous graphs
- On induced subgraphs of the cube
- Infinite distance transitive graphs of finite valency
- The equivalence of two problems on the cube
- Homogeneous graphs
- A short proof of Chvatal's Watchman Theorem
- Homogeneity conditions in graphs
- On the degree of Boolean functions as real polynomials
- Complexity measures and decision tree complexity: a survey.
- Sensitivity vs. block sensitivity of Boolean functions
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- CREW PRAM<scp>s</scp> and Decision Trees
- Invertibility of Toeplitz operators with polyanalytic symbols
- Universal graphs and universal functions
This page was built for publication: On the resolution of the sensitivity conjecture
