Fetching the paper…
Reading the bibliography…
Let $\Phi$ be a uniformly random $k$-SAT formula with $n$ variables and $m$ clauses.
A computing procedure for quantification theory
Martin Davis and Hilary Putnam · 1960
Earlier work this paper cites.
A machine program for theorem proving
Martin Davis, George Logemann, and Donald Loveland · 1961
Earlier work this paper cites.
The complexity of theorem proving procedures
Stephen Cook · 1971
Earlier work this paper cites.
The probabilistic analysis of some combinatorial search algorithms
Richard M. Karp · 1976
Earlier work this paper cites.
Average time analysis of simplified Davis-Putnam procedures
Allen T. Goldberg, Paul W. Purdom, and Cynthia Brown · 1982
Earlier work this paper cites.
σ 1 1 \sigma_{1}^{1} -formulae on finite structures
Miklós Ajtai · 1983
Earlier work this paper cites.
Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem
John Franco and Marvin Paull · 1983
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick L. Furst, James B. Saxe, and Michael Sipser · 1984
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Håstad · 1986
Earlier work this paper cites.
On the independence number of random graphs
Alan Frieze · 1990
Earlier work this paper cites.
Probabilistic analysis of a generalization of the unit-clause literal selection heuristic for the k k -satisfiability problem
Chao Ming-Te and John Franco · 1990
Earlier work this paper cites.
On selecting a satisfying truth assignment
Christos H. Papadimitriou · 1991
Earlier work this paper cites.
Mick gets some (the odds are on his side)
Václav Chvátal and Bruce Reed · 1992
Earlier work this paper cites.
The equivalence of two problems on the cube
Craig Gotsman and Nathan Linial · 1992
Earlier work this paper cites.
Analysis of two simple heuristics on a random instance of k k -SAT
Alan Frieze and Stephen Suen · 1996
Earlier work this paper cites.
Approximating the unsatisfiability threshold of random formulas
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C. Stamatiou · 1998
Earlier work this paper cites.
Analysis of random processes via and-or tree evaluation
Michael G. Luby, Michael Mitzenmacher, and M. Amin Shokrollahi · 1998
Earlier work this paper cites.
Short proofs are narrow – resolution made simple
Eli Ben-Sasson and Avi Wigderson · 1999
Earlier work this paper cites.
Optimal myopic algorithms for random 3 3 -SAT
Dimitris Achlioptas and Gregory B. Sorkin · 2000
Earlier work this paper cites.
Linear lower bound on degrees of positivstellensatz calculus proofs for the parity
Dima Grigoriev · 2001
Earlier work this paper cites.
Extensions to McDiarmid’s inequality when differences are bounded with high probability
Samuel Kutin · 2002
Earlier work this paper cites.
Analytic and algorithmic solution of random satisfiability problems
Marc Mézard, Giorgio Parisi, and Riccardo Zecchina · 2002
Earlier work this paper cites.
Exponential bounds for DPLL below the satisfiability threshold
Dimitris Achlioptas, Paul Beame, and Michael Molloy · 2004
Earlier work this paper cites.
Survey propagation: an algorithm for satisfiability
Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina · 2005
Earlier work this paper cites.
Gibbs states and the set of solutions of random constraint satisfaction problems
Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová · 2007
Earlier work this paper cites.
Solving constraint satisfaction problems through Belief Propagation-guided decimation
Andrea Montanari, Federico Ricci-Tersenghi, and Guilhem Semerjian · 2007
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
Pairs of SAT assignment in random boolean formulae
Hervé Daudé, Marc Mézard, Thierry Mora, and Riccardo Zecchina · 2008
Earlier work this paper cites.
Linear level lasserre lower bounds for certain k k -CSPs
Grant Schoenebeck · 2008
Earlier work this paper cites.
Random satisfiability
Dimitris Achlioptas · 2009
Cited alongside, same era.
Integrality gaps for sherali-adams relaxations
Moses Charikar, Konstantin Makarychev, and Yury Makarychev · 2009
Cited alongside, same era.
On smoothed k k -CNF formulas and the walksat algorithm
Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich, and Dan Vilenchik · 2009
Cited alongside, same era.
Message-passing algorithms for compressed sensing
David L. Donoho, Arian Maleki, and Andrea Montanari · 2009
Cited alongside, same era.
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Mohsen Bayati, David Gamarnik, and Prasad Tetali · 2010
Cited alongside, same era.
A better algorithm for random k k -SAT
Amin Coja-Oghlan · 2010
Cited alongside, same era.
The overlap gap property in principal submatrix recovery
David Gamarnik, Aukosh Jagannath, and Subhabrata Sen · 2019
Later among the works it cites.
The landscape of the planted clique problem: dense subgraphs and the overlap gap property
David Gamarnik and Ilias Zadik · 2019
Later among the works it cites.
Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira · 2019
Later among the works it cites.
Optimization of the Sherrington-Kirkpatrick hamiltonian
Andrea Montanari · 2019
Later among the works it cites.
Optimization of mean-field spin glasses
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The dynamics of message passing on dense graphs, with applications to compressed sensing
Mohsen Bayati and Andrea Montanari · 2011
Cited alongside, same era.
State evolution for general approximate message passing algorithms, with applications to spatial coupling
Adel Javanmard and Andrea Montanari · 2013
Cited alongside, same era.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Cited alongside, same era.
Analysis of Boolean functions
Ryan O’Donnell · 2014
Cited alongside, same era.
How to refute a random csp
Sarah R. Allen, Ryan O’Donnell, and David Witmer · 2015
Cited alongside, same era.
On independent sets in random graphs
Amin Coja-Oghlan and Charilaos Efthymiou · 2015
Cited alongside, same era.
Later among the works it cites.
Free energy wells and overlap gap property in sparse PCA
Gérard Ben Arous, Alexander S. Wein, and Ilias Zadik · 2020
Later among the works it cites.
Reducibility and statistical-computational gaps from secret leakage
Matthew Brennan and Guy Bresler · 2020
Later among the works it cites.
Detection thresholds in very sparse matrix completion
Charles Bordenave, Simon Coste, and Raj Rao Nadakuditi · 2020
Later among the works it cites.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein · 2020
Later among the works it cites.
Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni · 2020
Later among the works it cites.
Subexponential-time algorithms for sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira · 2020
Later among the works it cites.
Low-degree hardness of random optimization problems
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein · 2020
Later among the works it cites.
Tensor clustering with planted structures: statistical optimality and computational limits
Yuetian Luo and Anru R. Zhang · 2020
Later among the works it cites.
One-step replica symmetry breaking of random regular NAE- k k -SAT
Danny Nam, Allan Sly, and Youngtak Sohn · 2020
Later among the works it cites.
Computational barriers to estimation from low-degree polynomials
Tselil Schramm and Alexander S. Wein · 2020
Later among the works it cites.
Optimal low-degree hardness of maximum independent set
Alexander S. Wein · 2020
Later among the works it cites.
Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron
Emmanuel Abbe, Shuangping Li, and Allan Sly · 2021
Closest in time.
Statistical query algorithms and low-degree tests are almost equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, and Tselil Schramm · 2021
Closest in time.
Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein · 2021
Closest in time.
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik · 2021
Closest in time.
The overlap gap property and approximate message passing algorithms for p p -spin models
David Gamarnik and Aukosh Jagannath · 2021
Closest in time.
Circuit lower bounds for the p p -spin optimization problem
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein · 2021
Closest in time.
Algorithmic obstructions in the random number partitioning problem
David Gamarnik and Eren C. Kızıldağ · 2021
Closest in time.
A curious case of symmetric binary perceptron model: algorithms and barriers
David Gamarnik and Eren C. Kızıldağ · 2021
Closest in time.
Certifying solution geometry in random csps: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu · 2021
Closest in time.
Tight Lipschitz hardness for optimizing mean field spin glasses
Brice Huang and Mark Sellke · 2021
Closest in time.
Frozen 1 1 -RSB structure of the symmetric Ising perceptron
Will Perkins and Changji Xu · 2021
Closest in time.
Optimizing mean field spin glasses with external field
Mark Sellke · 2021
Closest in time.