Fetching the paper…
Reading the bibliography…
We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy.
R Tanner, A recursive approach to low complexity codes , IEEE Transactions on information theory 27
1981
Earlier work this paper cites.
Mikhael Gromov, Filling riemannian manifolds , Journal of Differential Geometry 18
1983
Earlier work this paper cites.
Noga Alon, Eigenvalues and expanders , Combinatorica 6
1986
Earlier work this paper cites.
Noga Alon and Fan RK Chung, Explicit construction of linear sized tolerant networks , Discrete Mathematics 72
1988
Earlier work this paper cites.
Moshe Morgenstern, Existence and explicit constructions of q+ 1 regular ramanujan graphs for every prime power q , Journal of Combinatorial Theory, Series B 62
1994
Earlier work this paper cites.
Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák, Lower bounds on hilbert’s nullstellensatz and propositional proofs , Proceedings of the London Mathematical Society 3
1996
Earlier work this paper cites.
Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo, Using the groebner basis algorithm to find proofs of unsatisfiability , Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 174–183
1996
Earlier work this paper cites.
A Robert Calderbank and Peter W Shor, Good quantum error-correcting codes exist , Physical Review A 54
1996
Earlier work this paper cites.
Andrew M Steane, Error correcting codes in quantum theory , Physical Review Letters 77
1996
Earlier work this paper cites.
Dima Grigoriev, Tseitin’s tautologies and lower bounds for nullstellensatz proofs , Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), IEEE, 1998, pp. 648–652
1998
Earlier work this paper cites.
Eli Ben-Sasson and Avi Wigderson, Short proofs are narrow—resolution made simple , Proceedings of the thirty-first annual ACM symposium on Theory of computing, 1999, pp. 517–526
1999
Earlier work this paper cites.
Sam Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi, Linear gaps between degrees for the polynomial calculus modulo distinct primes , Journal of Computer and System Sciences 62
2001
Earlier work this paper cites.
Noga Alon and Michael Capalbo, Explicit unique-neighbor expanders , The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., IEEE, 2002, pp. 73–79
2002
Earlier work this paper cites.
Subhash Khot, On the power of unique 2-prover 1-round games , Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002, pp. 767–775
2002
Earlier work this paper cites.
Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis, Towards strong nonapproximability results in the lovász-schrijver hierarchy , Proceedings of the thirty-seventh annual ACM symposium on theory of computing, 2005, pp. 294–303
2005
Earlier work this paper cites.
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of ramanujan complexes of type ad , European Journal of Combinatorics 26
2005
Earlier work this paper cites.
Irit Dinur, Madhu Sudan, and Avi Wigderson, Robust local testability of tensor products of ldpc codes , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, 2006, pp. 304–315
2006
Earlier work this paper cites.
Nathan Linial* and Roy Meshulam*, Homological connectivity of random 2-complexes , Combinatorica 26
2006
Earlier work this paper cites.
Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani, Tight integrality gaps for lovász-schrijver lp relaxations of vertex cover and max cut , Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 302–310
2007
Earlier work this paper cites.
Grant Schoenebeck, Linear level lasserre lower bounds for certain k-csps , 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 593–602
2008
Earlier work this paper cites.
Moses Charikar, Konstantin Makarychev, and Yury Makarychev, Integrality gaps for sherali-adams relaxations , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 283–292
2009
Earlier work this paper cites.
Claire Mathieu and Alistair Sinclair, Sherali-adams relaxations of the matching polytope , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 293–302
2009
Earlier work this paper cites.
Madhur Tulsiani, Csp gaps and reductions in the lasserre hierarchy , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 303–312
2009
Cited alongside, same era.
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis, Integrality gaps of 2-o(1) for vertex cover sdps in the lovász–schrijver hierarchy , SIAM Journal on Computing 39
2010
Cited alongside, same era.
Mikhail Gromov, Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry , Geometric and Functional Analysis 20
2010
Cited alongside, same era.
Prasad Raghavendra and David Steurer, Graph expansion and the unique games conjecture , Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 755–764
2010
Cited alongside, same era.
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid , Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 1–12
2019
Later among the works it cites.
Yotam Dikstein and Irit Dinur, Agreement testing theorems on layered set systems , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, pp. 1495–1524
2019
Later among the works it cites.
Noah Fleming, Pravesh Kothari, and Toniann Pitassi, Semialgebraic proofs and efficient algorithm design , Foundations and Trends in Theoretical Computer Science, 2019
2019
Later among the works it cites.
2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2012
Cited alongside, same era.
Prasad Raghavendra, David Steurer, and Madhur Tulsiani, Reductions between expansion problems , 2012 IEEE 27th Conference on Computational Complexity, IEEE, 2012, pp. 64–73
2012
Cited alongside, same era.
2014
Cited alongside, same era.
Tali Kaufman, David Kazhdan, and Alexander Lubotzky, Ramanujan complexes and bounded degree topological expanders , 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, IEEE, 2014, pp. 484–493
2014
Cited alongside, same era.
Boaz Barak, Siu On Chan, and Pravesh K Kothari, Sum of squares lower bounds from pairwise independence , Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 97–106
2015
Cited alongside, same era.
Siu On Chan, Approximation resistance from pairwise-independent subgroups , Journal of the ACM (JACM) 63
2016
Cited alongside, same era.
Shai Evra and Tali Kaufman, Bounded degree cosystolic expanders of every dimension , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 36–48
2016
Cited alongside, same era.
Irit Dinur and Tali Kaufman, High dimensional expanders imply agreement expanders , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 974–985
2017
Cited alongside, same era.
2020
Later among the works it cites.
2020
Later among the works it cites.
Shai Evra, Tali Kaufman, and Gilles Zémor, Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders , 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 218–227
2020
Later among the works it cites.
Tali Kaufman and Izhar Oppenheim, High order random walks: Beyond spectral gap , Combinatorica (2020), 1–37
2020
Later among the works it cites.
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer, Playing unique games on certified small-set expanders , STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 (Samir Khuller and Virginia Vassilevska Williams, eds.), ACM, 2021, pp. 1629–1642
2021
Later among the works it cites.
Nikolas P Breuckmann and Jens Niklas Eberhardt, Quantum low-density parity-check codes , PRX Quantum 2
2021
Later among the works it cites.
2021
Later among the works it cites.
2021
Later among the works it cites.
2021
Later among the works it cites.
Matthew B Hastings, Jeongwan Haah, and Ryan O’Donnell, Fiber bundle codes: breaking the n 1/2 polylog (n) barrier for quantum ldpc codes , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1276–1288
2021
Later among the works it cites.
2021
Later among the works it cites.
Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani, Near-linear time decoding of ta-shma’s codes via splittable regularity , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1527–1536
2021
Later among the works it cites.
Tali Kaufman and Ran J. Tessler, New cosystolic expanders from tensors imply explicit quantum LDPC codes with 𝑂𝑃𝐸𝑁 Ω ( ( n ) log k ( n ) ) \Omega(\sqrt{(}n)\log^{k}(n)) distance , STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, 2021, pp. 1317–1329
2021
Later among the works it cites.
2021
Later among the works it cites.
2022
Closest in time.
Anthony Leverrier and Gilles Zémor, Quantum tanner codes , arXiv preprint arXiv:2202.13641 (2022)
2022
Closest in time.
Kevin Pratt, Personal communication, March 2022
2022
Closest in time.