Fetching the paper…
Reading the bibliography…
Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability).
On discrete subgroups of the two by two projective linear group over 𝔭 {\mathfrak{p}} -adic fields
Yasutaka Ihara · 1966
Earlier work this paper cites.
On the Shannon capacity of a graph
László Lovász · 1979
Earlier work this paper cites.
Bounding the diameter of a distance-regular graph
Alexander Ivanov · 1983
Earlier work this paper cites.
Walk generating functions and spectral measures of infinite graphs
Chris Godsil and Bojan Mohar · 1988
Earlier work this paper cites.
A survey on spectra of infinite graphs
Bojan Mohar and Wolfgang Woess · 1989
Earlier work this paper cites.
The Ihara–Selberg zeta function of a tree lattice
Hyman Bass · 1992
Earlier work this paper cites.
Artin type L L -functions and the density theorem for prime cycles on finite graphs
Ki-ichiro Hashimoto · 1992
Earlier work this paper cites.
A note on coloring random k k -sets
Noga Alon and Joel Spencer · 1993
Earlier work this paper cites.
Laplacian eigenvalues and the maximum cut problem
Charles Delorme and Svatopluk Poljak · 1993
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel Goemans and David Williamson · 1995
Earlier work this paper cites.
Approximability of maximum splitting of k k -sets and some other APX-complete problems
Viggo Kann, Jens Lagergren, and Alessandro Panconesi · 1996
Earlier work this paper cites.
Spectra of regular graphs and hypergraphs and orthogonal polynomials
Wen-Ch’ing Winnie Li and Patrick Solé · 1996
Earlier work this paper cites.
Zeta functions of finite graphs and coverings
Harold Stark and Audrey Terras · 1996
Earlier work this paper cites.
Better approximation algorithms for Set Splitting and Not-All-Equal Sat
Gunnar Andersson and Lars Engebretsen · 1998
Earlier work this paper cites.
Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, and Madhu Sudan · 1998
Earlier work this paper cites.
Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint
Uri Zwick · 1998
Earlier work this paper cites.
Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems
Uri Zwick · 1999
Earlier work this paper cites.
Zeta functions of finite graphs
Motoko Kotani and Toshikazu Sunada · 2000
Earlier work this paper cites.
The phase transition in 1-in- k k SAT and NAE 3-SAT
Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, and Cristopher Moore · 2001
Cited alongside, same era.
The asymptotic order of the random k-sat threshold
Dimitris Achlioptas and Cristopher Moore · 2002
Cited alongside, same era.
Analytic and algorithmic solution of random satisfiability problems
Marc Mézard, Giorgio Parisi, and Riccardo Zecchina · 2002
Cited alongside, same era.
Bicolouring random hypergraphs
Tommaso Castellani, Vincenzo Napolano, Federico Ricci-Tersenghi, and Riccardo Zecchina · 2003
Cited alongside, same era.
Some results on random unsatisfiable k k -Sat instances and approximation algorithms applied to random structures
Andreas Goerdt and Tomasz Jurdziński · 2003
Cited alongside, same era.
Recognizing more random unsatisfiable 3 3 -SAT instances efficiently
Andreas Goerdt and André Lanka · 2003
Graph zeta function in the Bethe free energy and loopy belief propagation
Yusuke Watanabe and Kenji Fukumizu · 2009
Later among the works it cites.
On the number of perfect matchings in random lifts
Catherine Greenhill, Svante Janson, and Andrzej Ruciński · 2010
Later among the works it cites.
Limitations of Linear and Semidefinite Programs
Grant Schoenebeck · 2010
Later among the works it cites.
How to refute a random CSP
Sarah Allen, Ryan O’Donnell, and David Witmer · 2015
Later among the works it cites.
Invariant Gaussian processes and independent sets on regular graphs of large girth
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág · 2015
Later among the works it cites.
Constructing SAT filters with a quantum annealer
Adam Douglass, Andrew King, and Jack Raymond · 2015
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.
Maximizing quadratic programs: Extending Grothendieck’s inequality
Moses Charikar and Anthony Wirth · 2004
Cited alongside, same era.
MAX CUT in cubic graphs
Eran Halperin, Dror Livnat, and Uri Zwick · 2004
Cited alongside, same era.
Recognizing more unsatisfiable random k k -SAT instances efficiently
Joel Friedman, Andreas Goerdt, and Michael Krivelevich · 2005
Cited alongside, same era.
Witnesses for non-satisfiability of dense random 3CNF formulas
Uriel Feige, Jeong Han Kim, and Eran Ofek · 2006
Cited alongside, same era.
Threshold values of random k k -sat from the cavity method
Stephan Mertens, Marc Mézard, and Riccardo Zecchina · 2006
Cited alongside, same era.
Strong refutation heuristics for random k k -SAT
Amin Coja-Oghlan, Andreas Goerdt, and André Lanka · 2007
Cited alongside, same era.
Independence ratio and random eigenvectors in transitive graphs
Viktor Harangi and Bálint Virág · 2015
Later among the works it cites.
Independent sets and cuts in large-girth regular graphs
Endre Csóka · 2016
Later among the works it cites.
Satisfiability threshold for random regular NAE-SAT
Jian Ding, Allan Sly, and Nike Sun · 2016
Later among the works it cites.
How well do local algorithms solve semidefinite programs?
Zhou Fan and Andrea Montanari · 2016
Later among the works it cites.
Phase transitions in semidefinite relaxations
Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi · 2016
Later among the works it cites.
Non-backtracking random walks and a weighted Ihara’s theorem
Mark Kempton · 2016
Later among the works it cites.
Semidefinite programs on sparse random graphs and their application to community detection
Andrea Montanari and Subhabrata Sen · 2016
Later among the works it cites.
The Lovász theta function for random regular graphs and community detection in the hard regime
Jess Banks, Robert Kleinberg, and Cristopher Moore · 2017
Later among the works it cites.
A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts
Charles Bordenave · 2017
Later among the works it cites.
Sum of squares lower bounds for refuting any CSP
Pravesh Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Later among the works it cites.
Factors of IID on trees
Russell Lyons · 2017
Later among the works it cites.