@kirk86

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

. (2019)cite arxiv:1907.00847.

Abstract

In this paper, we show that every $(2^n-1+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $n$. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Description

[1907.00847] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Links and resources

URL:
BibTeX key:
huang2019induced
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication