Fetching the paper…
Reading the bibliography…
Partly on the basis of heuristic arguments from physics it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments.
M.-T. Chao, J. Franco: Probabilistic analysis of a generalization of the unit-clause literal selection heuristic for the k k -satisfiability problem. Inform. Sci. 51
1990
Earlier work this paper cites.
P. Cheeseman, B. Kanefsky, W. Taylor: Where the really
1991
Earlier work this paper cites.
C. H. Papadimitriou: On selecting a satisfying truth assignment. Proc. 32nd FOCS (1991) 163–169
1991
Earlier work this paper cites.
V. Chvátal, B. Reed: Mick gets some (the odds are on his side). Proc. 33th FOCS (1992) 620–627
1992
Earlier work this paper cites.
D. Mitchell, B. Selman, H. Levesque: Hard and easy distribution of SAT problems. Proc. 10th AAAI (1992) 459–465
1992
Earlier work this paper cites.
A. Broder, A. Frieze, E. Upfal: On the satisfiability and maximum satisfiability of random 3-CNF formulas. Proc. 4th SODA (1993) 322–330
1993
Earlier work this paper cites.
A. Frieze, S. Suen: Analysis of two simple heuristics on a random instance of k k -SAT. Journal of Algorithms 20
1996
Earlier work this paper cites.
B. Selman, H. Kautz, B. Cohen: Local search strategies for satisfiability testing. In David S. Johnson, Michael A. Trick (eds.): Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26
1996
Earlier work this paper cites.
U. Schöning: A probabilistic algorithm for k k -SAT and constraint satisfaction problems. Proc. 40th FOCS (1999) 410–414
1999
Earlier work this paper cites.
S. Janson, T. Łuczak, A. Ruciński: Random Graphs, Wiley 2000
2000
Earlier work this paper cites.
D. Achlioptas: Lower bounds for random 3-SAT via differential equations. Theoretical Computer Science 265
2001
Earlier work this paper cites.
M. Alekhnovich, E. Ben-Sasson: Analysis of the random walk algorithm on random 3-CNFs. unpublished (2002)
2002
Earlier work this paper cites.
T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe: A Probabilistic 3-SAT Algorithm Further Improved. Proc. 19th STACS (2002) 192–202
2002
Earlier work this paper cites.
M. Mézard, G. Parisi, R. Zecchina: Analytic and algorithmic solution of random satisfiability problems. Science 297
2002
Cited alongside, same era.
M. Hajiaghayi, G. Sorkin: The satisfiability threshold of random 3-SAT is at least 3.52 3.52 . IBM Research Report RC22942 (2003)
2003
Cited alongside, same era.
2003
Cited alongside, same era.
D. Achlioptas, P. Beam, M. Molloy: Exponential bounds for DPLL below the satisfiability threshold. Proc. SODA (2004)
2004
Cited alongside, same era.
D. Achlioptas, Y. Peres: The threshold for random k k -SAT is 2 k ln 2 − O ( k ) 2^{k}\ln 2-O(k) . Journal of the AMS 17
2004
Cited alongside, same era.
D. Achlioptas, A. Coja-Oghlan: Algorithmic barriers from phase transitions. Proc. 49th FOCS (2008) 793–802
2008
Later among the works it cites.
A. Coja-Oghlan: A better algorithm for random k k -SAT. SIAM J. Computing 39
2010
Later among the works it cites.
D. Achlioptas, A. Coja-Oghlan, F. Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. Random Structures and Algorithms 38
2011
Later among the works it cites.
A. Coja-Oghlan: On belief propagation guided decimation for random k k -SAT. Proc. 22nd SODA (2011) 957–966
2011
Later among the works it cites.
T. Hertli, R. Moser, D. Scheder: Improving PPSZ for 3-SAT using critical variables. Proc. 28th STACS (2011) 237–248
2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
K. Iwama, S. Tamaki: Improved Upper Bounds for 3-SAT. Proc. 15th SODA (2004) 328–328
2004
Cited alongside, same era.
E. Dantsin, A. Wolpert: An improved upper bound for SAT. Proc. 8th SAT (2005) 400–407
2005
Cited alongside, same era.
M. Molloy: Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27
2005
Cited alongside, same era.
R. Paturi, P. Pudlák, M. Saks, F. Zane: An Improved Exponential-time Algorithm for k-SAT. J. ACM 52
2005
Cited alongside, same era.
D. Achlioptas, C. Moore: Random k k -SAT: two moments suffice to cross a sharp threshold. SIAM Journal on Computing 36
2006
Cited alongside, same era.
M. Alekhnovich, E. Ben-Sasson: Linear upper bounds for random walk on small density random 3-CNFs. SIAM Journal on Computing 36
2006
Cited alongside, same era.
A. Kaporis, L. Kirousis, E. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures and Algorithms 28
2006
Cited alongside, same era.
A. Coja-Oghlan, A. Frieze: Analysing Walksat on random formulas. SIAM Journal on Computing 43
2014
Later among the works it cites.
D. Gamarnik, M. Sudan: Limits of local algorithms over sparse random graphs. Proc. of 5th ICTS (2014) 369–376
2014
Later among the works it cites.
D. Gamarnik, M. Sudan: Performance of Survey Propagation guided decimation algorithm for the random NAE- K K -SAT problem. arXiv 1402.0052v2 (2014)
2014
Later among the works it cites.
T. Hertli: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. SIAM J. Comput. 43
2014
Later among the works it cites.
J. Ding, A. Sly, N. Sun: Proof of the satisfiability conjecture for large k k . Proc. 47th STOC (2015) 59–68
2015
Later among the works it cites.
A. Braunstein, L. Dall-Asta, G. Semerjian, L. Zdeborová: The large deviations of the whitening process in random constraint satisfaction problems. Journal of Statitstical Mechanics: Theory and Experiment 5
2016
Closest in time.
A. Coja-Oghlan, K. Panagiotou: The asymptotic k k -SAT threshold. Advances in Mathematics 288
2016
Closest in time.
S. Hetterich: Analysing Survey Propagation Guided Decimation on Random Formulas. Proc. of 43rd ICALP (2016) in press
2016
Closest in time.