The landscape of the planted clique problem: dense subgraphs and the overlap gap property

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

Unnamed Item
Unnamed Item
Algorithmic thresholds for tensor PCA
Finding hidden cliques of size $\sqrt{N/e}$ in nearly linear time
Expected complexity of graph partitioning problems
Notes on computational-to-statistical gaps: predictions using statistical physics
Dense subgraphs in random graphs
Finding a large submatrix of a Gaussian random matrix
The satisfiability threshold for random linear equations
Local algorithms for independent sets are half-optimal
On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
The all-or-nothing phenomenon in sparse linear regression
The overlap gap property and approximate message passing algorithms for $p$-spin models
Computational and statistical boundaries for submatrix localization in a large noisy matrix
Suboptimality of local algorithms for a class of max-cut problems
BOUNDS ON TAIL PROBABILITIES OF DISCRETE DISTRIBUTIONS
Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
Reconstruction and Clustering in Random Constraint Satisfaction Problems
On independent sets in random graphs
Large Cliques Elude the Metropolis Process
On colouring random graphs
Two‐coloring random hypergraphs
Community Detection and Stochastic Block Models
Analysing Survey Propagation Guided Decimation on Random Formulas
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
Optimization on sparse random hypergraphs and spin glasses
Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
Reducibility among Combinatorial Problems
Spurious Valleys in Two-layer Neural Network Optimization Landscapes
Walksat Stalls Well Below Satisfiability
Gibbs states and the set of solutions of random constraint satisfaction problems
Finding Hidden Cliques in Linear Time with High Probability
On the solution‐space geometry of random constraint satisfaction problems
Mean Field Models for Spin Glasses
Limits of local algorithms over sparse random graphs
Free Energy Wells and Overlap Gap Property in Sparse PCA

This page was built for publication: The landscape of the planted clique problem: dense subgraphs and the overlap gap property