Fetching the paper…
Reading the bibliography…
The MaxClique problem, finding the largest complete subgraph in an Erd{\"o}s-R{\'e}nyi $G(N,p)$ random graph in the large $N$ limit, is a well-known example of a simple problem for which finding any approximate solution within a factor of $2$ of the known, probabilistically determined limit, appears to require P$=$NP.
P. Erdös and A. Rényi, “On random graphs, i,” Publicationes Mathematicae (Debrecen)
1959
Earlier work this paper cites.
Wiley, January 1968
W. Feller, An Introduction to Probability Theory and Its Applications · 1968
Earlier work this paper cites.
D. W. Matula, “On the complete subgraphs of a random graph,” Combinatory mathematics and its Applications
1970
Earlier work this paper cites.
D. W. Matula, “Employee party problem,” in Notices of the American Mathematical Society
1972
Earlier work this paper cites.
G. R. Grimmett and C. J. McDiarmid, “On colouring random graphs,” in Mathematical Proceedings of the Cambridge Philosophical Society
1975
Earlier work this paper cites.
B. Bollobás and P. Erdös, “Cliques in random graphs,” in Mathematical Proceedings of the Cambridge Philosophical Society
1976
Earlier work this paper cites.
Department of Computer Science, Southern Methodist University, 1976
D. W. Matula, The largest clique size in a random graph · 1976
Earlier work this paper cites.
S. Kirkpatrick and R. H. Swendsen, “Statistical mechanics and disordered systems,” Communications of the ACM
1985
Earlier work this paper cites.
A. M. Frieze, “On the independence number of random graphs,” Discrete Mathematics
1990
Earlier work this paper cites.
L. Kučera, “A generalized encryption scheme based on random graphs,” in International Workshop on Graph-Theoretic Concepts in Computer Science
1991
Earlier work this paper cites.
M. Jerrum, “Large cliques elude the metropolis process,” Random Structures & Algorithms
1992
Earlier work this paper cites.
B. Selman, H. A. Kautz, B. Cohen, et al
1993
Earlier work this paper cites.
S. Kirkpatrick and B. Selman, “Critical behavior in the satisfiability of random boolean expressions,” Science
1994
Earlier work this paper cites.
L. A. Sanchis, “Test case construction for the vertex cover,” in Computational Support for Discrete Mathematics: DIMACS Workshop, March 12-14, 1992
1994
Cited alongside, same era.
L. Kučera, “Expected complexity of graph partitioning problems,” Discrete Applied Mathematics
1995
Cited alongside, same era.
American Mathematical Soc., 1996
D. S. Johnson and M. A. Trick, Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993 · 1996
Cited alongside, same era.
M. Brockington and J. C. Culberson, “Camouflaging independent sets in quasi-random graphs,” Cliques, coloring, and satisfiability: second DIMACS implementation challenge
1996
Cited alongside, same era.
Springer, 1998
B. Bollobás, Modern graph theory · 1998
Cited alongside, same era.
P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient belief propagation for early vision,” International journal of computer vision
2006
Later among the works it cites.
F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, “Gibbs states and the set of solutions of random constraint satisfaction problems,” Proceedings of the National Academy of Sciences
2007
Later among the works it cites.
2007
Later among the works it cites.
M. Mézard and A. Montanari, “Constraint satisfaction networks in physics and computation,” Clarendon Press, Oxford
2007
Later among the works it cites.
Oxford University Press, 2009
M. Mezard and A. Montanari, Information, physics, and computation · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
1998
Cited alongside, same era.
B. J. Frey and D. J. MacKay, “A revolution: Belief propagation in graphs with cycles,” in Advances in neural information processing systems
1998
Cited alongside, same era.
J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Generalized belief propagation,” in Advances in neural information processing systems
2001
Cited alongside, same era.
M. Mézard, G. Parisi, and R. Zecchina, “Analytic and algorithmic solution of random satisfiability problems,” Science
2002
Cited alongside, same era.
I. Ipsen and R. M. Wills, “Analysis and computation of google’s pagerank,” in 7th IMACS international symposium on iterative methods in scientific computing, Fields Institute, Toronto, Canada
2005
Cited alongside, same era.
J. M. Mooij and H. J. Kappen, “Sufficient conditions for convergence of loopy belief propagation,” in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence
2005
Cited alongside, same era.
F. Panneton, P. L’ecuyer, and M. Matsumoto, “Improved long-period generators based on linear recurrences modulo 2,” ACM Transactions on Mathematical Software (TOMS)
2006
Cited alongside, same era.
Later among the works it cites.
Y. Dekel, O. Gurel-Gurevich, and Y. Peres, “Finding hidden cliques in linear time with high probability,” Combinatorics, Probability and Computing
2014
Later among the works it cites.
Y. Deshpande and A. Montanari, “Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time,” Foundations of Computational Mathematics
2015
Later among the works it cites.
C. Sanderson and R. Curtin, “Armadillo: a template-based c++ library for linear algebra,” Journal of Open Source Software
2016
Later among the works it cites.
Q. Lei, K. Zhong, and I. S. Dhillon, “Coordinate-wise power method,” in Advances in Neural Information Processing Systems
2016
Later among the works it cites.
R. Marino, G. Parisi, and F. Ricci-Tersenghi, “The backtracking survey propagation algorithm for solving random K-SAT
2016
Later among the works it cites.
R. R. Curtin, M. Edel, M. Lozhnikov, Y. Mentekidis, S. Ghaisas, and S. Zhang, “mlpack 3: a fast, flexible machine learning library,” Journal of Open Source Software
2018
Closest in time.
M. C. Angelini and F. Ricci-Tersenghi, “In preparation,” 2018
2018
Closest in time.