DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2020.62

Sensitivity Lower Bounds from Linear Dependencies

Authors: Sophie Laplante, Reza Naserasr, and Anupa Sunny

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H_n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by s₀(f) s₁(f), a strictly stronger statement which implies the sensitivity conjecture.

Cite as

Sophie Laplante, Reza Naserasr, and Anupa Sunny. Sensitivity Lower Bounds from Linear Dependencies. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.MFCS.2020.62,
  author =	{Laplante, Sophie and Naserasr, Reza and Sunny, Anupa},
  title =	{{Sensitivity Lower Bounds from Linear Dependencies}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.62},
  URN =		{urn:nbn:de:0030-drops-127320},
  doi =		{10.4230/LIPIcs.MFCS.2020.62},
  annote =	{Keywords: Boolean Functions, Polynomial Degree, Sensitivity}
}

Search Results

Documents authored by Naserasr, Reza

Sensitivity Lower Bounds from Linear Dependencies

Abstract

Cite as

Thanks for your feedback!

Could not send message