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 (55)
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 ⋮ Hardness self-amplification: simplified, optimized, and unified ⋮ Average-case complexity of tensor decomposition for low-degree polynomials ⋮ Algorithms approaching the threshold for semi-random planted clique ⋮ 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
This page was built for publication: Large Cliques Elude the Metropolis Process
