Fetching the paper…

Reading the bibliography…

2020

Explicit SoS lower bounds from high-dimensional expanders

Dinur, Irit, Filmus, Yuval, Harsha, Prahladh et al.

Original
PDF
Post on X

Understand

We construct an explicit family of 3XOR instances which is hard for $O(\sqrt{\log n})$ levels of the Sum-of-Squares hierarchy.

In contrast to earlier constructions, which involve a random component, our systems 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).

Explicit SoS lower bounds from high-dimensional expanders · Around

Built on

Filling Riemannian manifolds
1983
Earlier work this paper cites.
Metric Spaces of Non-Positive Curvature , volume 319 of
1999
Earlier work this paper cites.
Short proofs are narrow - resolution made simple
2001
Earlier work this paper cites.
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
2001
Earlier work this paper cites.
Ramanujan complexes of type A d ~ \tilde{A_{d}}
——— · 2005
Earlier work this paper cites.
Notes on Gromov’s systolic estimate
2006
Earlier work this paper cites.

Similar

A Mooore bound for simplicial complexes
2007
Cited alongside, same era.
Buildings, Theory and applications , volume 248 of
2008
Cited alongside, same era.
Linear level Lasserre lower bounds for certain k-CSPs
2008
Cited alongside, same era.
A short proof of Gromov’s filling inequality
2008
Cited alongside, same era.
CSP gaps and reductions in the Lasserre hierarchy
2009
Cited alongside, same era.
Approximation resistance from pairwise-independent subgroups
2012
Cited alongside, same era.
List decoding of direct sum codes
Cited in the paper.
Approximating constraint satisfaction problems on high-dimensional expanders
Original
Cited in the paper.
Improved analysis of higher order random walks and applications
Cited in the paper.
Spectral independence in high-dimensional expanders and applications to the hardcore model
Original
Cited in the paper.
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
Original
Cited in the paper.
Rounding semidefinite programming hierarchies via global correlation
Original
Cited in the paper.

Then

Buildings and their applications in geometry and topology
2012
Later among the works it cites.
Mixing properties and the chromatic number of Ramanujan Complexes
Original
2015
Later among the works it cites.
Isoperimetric inequalities for Ramanujan complexes and topological expanders
Original
2016
Later among the works it cites.
Good distance lattices from high dimensional expanders , 2018
Original
2018
Later among the works it cites.
Semialgebraic proofs and efficient algorithm design
2019
Later among the works it cites.
Decodable quantum LDPC codes beyond the n \sqrt{n} distance barrier using high dimensional expanders , 2020

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2020

Closest in time.