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

zbMATH Keywords

Boolean functionsensitivity conjecture

Mathematics Subject Classification ID

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)

An induced subgraph of the Hamming graph with maximum degree 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