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