Parallel Tempering for the planted clique problem

Abstract

The theoretical information threshold for the planted clique problem is $2{\log }_2(N)$, however no polynomial algorithm is known to recover a planted clique of size $O(N^{1/2-\epsilon })$, $\epsilon >0$. In this paper we will apply a standard method for the analysis of disordered models, the Parallel-Tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the Sparse Planted Independent Set problem. In this situation thresholds should be sharper and finite size corrections should be less important. Also in this case PT shows a polynomial scaling in the hard region for the recovery.

arXiv comment12 pages, 5 figures

References in corpus (11)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics-based reconstruction in compressed sensing
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Computational barriers in minimax submatrix detection
• Finding One Community in a Sparse Graph
• Computational Lower Bounds for Sparse PCA
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Statistical mechanics of the vertex-cover problem
• The hard-core model on random graphs revisited
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix

Cited by in corpus (9)

• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Hard Optimization Problems have Soft Edges
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Revisiting the Challenges of MaxClique
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model