HackerPapers

arXiv:1907.00847math.CO

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Hao Huang

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 $\sqrt{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.

arXiv comments
Journal reference
DOI
Subjects
math.COCombinatorics cs.CCComputational Complexity

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 2 threads, from Jul 2019 to Oct 2021. Found in 3 HN submissions from Aug 2019 to Sep 2020. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. [dead] 1 comment

    • For those who want a real deep dive, I recommend this video course on Analysis of Boolean Functions from Ryan O'Donnell: https://www.youtube.com/watch?v=JIruJ8edYYM https://www.cs.cmu.edu/~odonnell/boolean-analysis/ And his book…

      amirhirschView on HNParent context

  2. Decades-Old Computer Science Conjecture Solved in Two Pages 2 comments

    • On boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea... The closing quote: > [Huang] was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least √n of the…

      floatingatollView on HNParent context

    • nice use of a single .tex file to produce the full .pdf https://arxiv.org/e-print/1907.00847 (rename to 1907.00847.tex and then latexmk -pdf 1907.00847.tex)

      plgView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.