Large Cliques Elude the Metropolis Process
From MaRDI portal
Publication:4019371
DOI10.1002/rsa.3240030402zbMath0754.60018WikidataQ56210421 ScholiaQ56210421MaRDI QIDQ4019371
Publication date: 16 January 1993
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240030402
Related Items
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time, Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model, The Complexity of Public-Key Cryptography, Hard graphs for randomized subgraph exclusion algorithms, Hidden Hamiltonian Cycle Recovery via Linear Programming, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Finding a planted clique by adaptive probing, Finding Hidden Cliques in Linear Time with High Probability, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Free Energy Wells and Overlap Gap Property in Sparse PCA, Coloring random graphs, Optimal detection of sparse principal components in high dimension, Comment on ``Hypothesis testing by convex optimization, The complexity of explicit constructions, Maximum cliques in graphs with small intersection number and random intersection graphs, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, Some spin glass ideas applied to the clique problem, Finding one community in a sparse graph, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, What do we know about the Metropolis algorithm?, The Metropolis algorithm for graph bisection, A simple spectral algorithm for recovering planted partitions, Revisiting simulated annealing: a component-based analysis, A slowly mixing Markov chain with implications for Gibbs sampling, Recovering nonuniform planted partitions via iterated projection, On the computational tractability of statistical estimation on amenable graphs, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Isotonic regression with unknown permutations: statistics, computation and adaptation, Tensor clustering with planted structures: statistical optimality and computational limits, Statistical and computational limits for sparse matrix detection, Speeding up branch and bound algorithms for solving the maximum clique problem, On the hardness of designing public signals, Metastability in stochastic replicator dynamics, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Computational barriers in minimax submatrix detection, Energy landscape for large average submatrix detection problems in Gaussian random matrices, Some lower bounds in parameterized \(\mathrm{AC}^{0}\), Improvements to MCS algorithm for the maximum clique problem, Finding large cliques in sparse semi-random graphs by simple randomized search heuristics, A new genetic algorithm, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements, The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture, Parallel tempering for the planted clique problem, On independent sets in random graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics
