License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.38
URN: urn:nbn:de:0030-drops-135774
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13577/
Go to the corresponding LIPIcs Volume Portal

Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh ; Tulsiani, Madhur

Explicit SoS Lower Bounds from High-Dimensional Expanders

pdf-format:
LIPIcs-ITCS-2021-38.pdf (0.5 MB)

Abstract

We construct an explicit and structured family of 3XOR instances which is hard for O(√{log n}) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems are highly structured and can be constructed explicitly in deterministic polynomial time.
Our construction is based on the high-dimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov.
Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author (FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a high-dimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.

BibTeX - Entry

@InProceedings{dinur_et_al:LIPIcs.ITCS.2021.38,
  author =	{Irit Dinur and Yuval Filmus and Prahladh Harsha and Madhur Tulsiani},
  title =	{{Explicit SoS Lower Bounds from High-Dimensional Expanders}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13577},
  URN =		{urn:nbn:de:0030-drops-135774},
  doi =		{10.4230/LIPIcs.ITCS.2021.38},
  annote =	{Keywords: High-dimensional expanders, sum-of-squares, integrality gaps}
}

Keywords: High-dimensional expanders, sum-of-squares, integrality gaps
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI