Parallel Tempering for the planted clique problem
Not on the map. Why?
Abstract (arXiv)
The theoretical information threshold for the planted clique problem is 2log2(N), however no polynomial algorithm is known to recover a planted clique of size O(N1/2-ε), ε>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.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Feb 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2022: 3; 2023: 1; 2024: 1.
5 papers.
- 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
- 2022On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributionscited by 6
- 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problemscited by 3
- 2022Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learningcited by 1
- 2024A short review on the maximum clique problem algorithms with classical, AI, and quantum methodscited by 0
- 2024A short review on the maximum clique problem algorithms with classical, AI, and quantum methods13 Mar 2024
- 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems11 Sep 2023
- 2022On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions5 Sep 2022
- 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set27 Jun 2022
- 2022Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning5 Jan 2022