Fetching the paper…
Reading the bibliography…
We consider the problem of approximately solving constraint satisfaction problems with arity $k > 2$ ($k$-CSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs.
The regularity lemma and approximation schemes for dense problems
A. Frieze and R. Kannan · 1996
Earlier work this paper cites.
Some Canonical Sequences of Integers
M. Bernstein and N. J. A. Sloane · 2002
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Earlier work this paper cites.
Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations
Martin J Wainwright and Michael I Jordan · 2004
Earlier work this paper cites.
Some 3CNF properties are hard to test
Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova · 2005
Earlier work this paper cites.
Explicit constructions of ramanujan complexes of type ad
Alexander Lubotzky, Beth Samuels, and Uzi Vishne · 2005
Earlier work this paper cites.
Ramanujan complexes of typeãd
Alexander Lubotzky, Beth Samuels, and Uzi Vishne · 2005
Earlier work this paper cites.
Unique games on expanding constraint graphs are easy
Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth Vishnoi · 2008
Earlier work this paper cites.
Rounding semidefinite programming hierarchies via global correlation
Boaz Barak, Prasad Raghavendra, and David Steurer · 2011
Earlier work this paper cites.
Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives
Venkatesan Guruswami and Ali Kemal Sinop · 2011
Earlier work this paper cites.
How to play unique games on expanders
Konstantin Makarychev and Yury Makarychev · 2011
Earlier work this paper cites.
Locally testable codes and expanders
Irit Dinur and Tali Kaufman · 2012
Earlier work this paper cites.
Faster SDP hierarchy solvers for local rounding algorithms
Venkatesan Guruswami and Ali Kemal Sinop · 2012
Earlier work this paper cites.
Guest column: The quantum PCP conjecture
Dorit Aharonov, Itai Arad, and Thomas Vidick · 2013
Cited alongside, same era.
Product-state approximations to quantum ground states
Fernando G. S. L. Brandão and Aram Wettroth Harrow · 2013
Cited alongside, same era.
The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions
B.E. Sagan · 2013
Cited alongside, same era.
Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
Yuichi Yoshida and Yuan Zhou · 2014
Cited alongside, same era.
Erdős-Ko-Rado Theorems: Algebraic Approaches
Christopher Godsil and Karen Meagher · 2015
Cited alongside, same era.
A new regularity lemma and faster approximation algorithms for low threshold rank graphs
Shayan Oveis Gharan and Luca Trevisan · 2015
Random walks on Ramanujan complexes and digraphs
Eyal Lubetzky, Alex Lubotzky, and Ori Parzanchevski · 2017
Later among the works it cites.
A birthday repetition theorem and complexity of approximating dense csps
Pasin Manurangsi and Prasad Raghavendra · 2017
Later among the works it cites.
On the bit complexity of sum-of-squares proofs
Prasad Raghavendra and Benjamin Weitz · 2017
Later among the works it cites.
Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant · 2018
Later among the works it cites.
Hypergraph expanders of all uniformities from Cayley graphs
David Conlon, Jonathan Tidor, and Yufei Zhao · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
An orthogonal basis for functions over a slice of the boolean hypercube
Yuval Filmus · 2016
Cited alongside, same era.
Isoperimetric inequalities for ramanujan complexes and topological expanders
Tali Kaufman, David Kazhdan, and Alexander Lubotzky · 2016
Cited alongside, same era.
Isoperimetric inequalities in simplicial complexes
Ori Parzanchevski, Ron Rosenthal, and Ran J. Tessler · 2016
Cited alongside, same era.
High dimensional expanders imply agreement expanders
Irit Dinur and Tali Kaufman · 2017
Cited alongside, same era.
High dimensional random walks and colorful expansion
Tali Kaufman and David Mass · 2017
Cited alongside, same era.
Sum of squares lower bounds for refuting any CSP
Pravesh Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Cited alongside, same era.
Boolean function analysis on high-dimensional expanders
Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha · 2018
Later among the works it cites.
List decoding with double samplers
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma · 2018
Later among the works it cites.
Good distance lattices from high dimensional expanders
Tali Kaufman and David Mass · 2018
Later among the works it cites.
Construction of new local spectral high dimensional expanders
Tali Kaufman and Izhar Oppenheim · 2018
Later among the works it cites.
High order random walks: Beyond spectral gap
Tali Kaufman and Izhar Oppenheim · 2018
Later among the works it cites.
List decoding of direct sum codes
Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani · 2019
Closest in time.
Agreement testing theorems on layered set systems
Yotam Dikstein and Irit Dinur · 2019
Closest in time.