Fetching the paper…
Reading the bibliography…
In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size $k$ is planted in an Erdos Renyi graph $G(n,\frac{1}{2})$ resulting in a graph $G\left(n,\frac{1}{2},k\right)$.
Reducibility among combinatorial problems
Richard M Karp · 1972
Earlier work this paper cites.
On colouring random graphs
G. Grimmett and C. McDiarmid · 1975
Earlier work this paper cites.
Large cliques elude the metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Expected complexity of graph partitioning problems
Luděk Kučera · 1995
Earlier work this paper cites.
Finding a large hidden clique in a random graph
Noga Alon, Michael Krivelevich, and Benny Sudakov · 1998
Earlier work this paper cites.
Bounds on tail probabilities of discrete distributions
Bernhard Klar · 2000
Earlier work this paper cites.
Random Graphs
Bela Bollobas · 2001
Earlier work this paper cites.
Two-coloring random hypergraphs
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, and Prasad Tetali · 2002
Earlier work this paper cites.
Clustering of solutions in the random satisfiability problem
M. Mézard, T. Mora, and R. Zecchina · 2005
Earlier work this paper cites.
Gibbs states and the set of solutions of random constraint satisfaction problems
F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová · 2007
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Earlier work this paper cites.
Mean Field Models for Spin Glasses: Volume I: Basic Examples
M. Talagrand · 2010
Earlier work this paper cites.
On the solution space geometry of random formulas
D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi · 2011
Earlier work this paper cites.
On independent sets in random graphs
A. Coja-Oghlan and C. Efthymiou · 2011
Earlier work this paper cites.
Reconstruction and clustering in random constraint satisfaction problems
Andrea Montanari, Ricardo Restrepo, and Prasad Tetali · 2011
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Y. Deshpande and A. Montanari · 2013
Cited alongside, same era.
Finding hidden cliques in linear time with high probability
Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres · 2014
Cited alongside, same era.
Local algorithms for independent sets are half-optimal
Mustazee Rahman and Balint Virag · 2014
Cited alongside, same era.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin · 2016
Cited alongside, same era.
Spurious local minima are common in two-layer relu neural networks
Itay Safran and Ohad Shamir · 2017
Later among the works it cites.
Algorithmic thresholds for tensor pca
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath · 2018
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
Later among the works it cites.
Dense subgraphs in random graphs
Paul Balister, Bela Bollobas, Julian Sahasrabudhe, and Alexander Veremyev · 2018
Later among the works it cites.
Information-theoretic bounds and phase transitions in clustering, space pca, and submatrix localization
J. Banks, C. Moore, Vershynin R., N. Verzelen, and J. Xu · 2018
Later among the works it cites.
Notes on computational-statistical gaps: predictions using statistical physics
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Amin Coja-Oghlan, Amir Haqshenas, and Samuel Hetterich · 2016
Cited alongside, same era.
Finding a large submatrix of a gaussian random matrix
David Gamarnik and Quan Li · 2016
Cited alongside, same era.
Analysing survey propagation guided decimation on random formulas
Samuel Hetterich · 2016
Cited alongside, same era.
Average-case hardness of rip certification
Tengyao Wang, Quentin Berthet, and Yaniv Plan · 2016
Cited alongside, same era.
Community detection and stochastic block models: recent developments
Emmanuel Abbe · 2017
Cited alongside, same era.
The satisfiability threshold for random linear equations
Peter Ayre, Amin Coja-Oghlan, Pu Gao, and Noela Muller · 2017
Cited alongside, same era.
Suboptimality of local algorithms for a class of max-cut problems, 2017
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman · 2017
Cited alongside, same era.
Afonso S Bandeira, Amelia Perry, and Alexander S. Wein · 2018
Later among the works it cites.
On the unbalanced cut problem and the generalized sherrington-kickpatrick model
Aukosh Jagannath and Subhabrata Sen · 2018
Later among the works it cites.
Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang · 2018
Later among the works it cites.
Optimization of the sherrington-kirkpatrick hamiltonian
Andrea Montanari · 2018
Later among the works it cites.
Following the ground-states of full-rsb spherical spin glasses
Eliran Subag · 2018
Later among the works it cites.
Spurious valleys in two-layer neural network optimization landscapes
Luca Venturi, Afonso S Bandeira, and Joan Bruna · 2018
Later among the works it cites.
Statistical problems with planted structures: Information theoretical and computational limits
Yihong Wu and Jiaming Xu · 2018
Later among the works it cites.
Benefit of over-parameterization with em
Ji Xu, Daniel Hsu, and Arian Maleki · 2018
Later among the works it cites.
The overlap gap property and approximate message passing algorithms for p p -spin models
David Gamarnik and Aukosh Jagannath · 2019
Closest in time.
The all-or-nothing phenomenon in sparse linear regression
Galen Reeves, Jiaming Xu, and Ilias Zadik · 2019
Closest in time.