Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

On induced subgraphs of the cube,

F. Chung, Z. Füredi, R. Graham, P. Seymour, · 1988

Earlier work this paper cites.

CREW PRAMs and decision trees,

N. Nisan, · 1989

Earlier work this paper cites.

The equivalence of two problems on the cube

C. Gotsman, N. Linial, · 1992

Earlier work this paper cites.

On the degree of Boolean functions as real polynomials,

N. Nisan, M. Szegedy, · 1992

Earlier work this paper cites.

Sensitivity vs. block sensitivity of Boolean functions,

D. Rubinstein, · 1995

Earlier work this paper cites.

Complexity measures and decision tree complexity: a survey,

H. Buhrman, R. de Wolf, · 2002

Cited alongside, same era.

Sensitivity, block sensitivity, and ℓ \ell -block sensitivity of Boolean functions,

C. Kenyon, S. Kutin, · 2004

Cited alongside, same era.

A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices,

S. Fisk, · 2005

Cited alongside, same era.

New separation between s ⁡ ( f ) s(f) and b ​ s ​ ( f ) bs(f) ,

A. Ambainis, X. Sun, · 2011

Cited alongside, same era.

Variations on the Sensitivity Conjecture,

P. Hatami, R. Kulkarni, D. Pankratov, · 2011

Cited alongside, same era.

Properties and applications of boolean function composition,

A. Tal,

Cited in the paper.

Sensitivity versus block sensitivity of boolean functions,

M. Virza, · 2011

Later among the works it cites.

A new approach to the sensitivity conjecture,

J. Gilmer, M. Koucký, M. Saks, · 2015

Later among the works it cites.

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions, 7th Innovations in Theoretical Computer Science Conference (ITCS), 2016

P. Gopalan, N. Nisan, R. Servedio, K. Talwar, and A. Wigderson, · 2016

Later among the works it cites.

Degree and sensitivity: tails of two distributions,

P. Gopalan, R. Servedio, A. Tal, A. Wigderson, · 2016

Later among the works it cites.

A note on a communication game, CoRR, abs/1706.07890, 2017

Original

A. Drucker, · 2017

Later among the works it cites.