scientific article; zbMATH DE number 1380608

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W" /><457::AID-RSA14>3.0.CO;2-W 10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-WzbMath0959.05082WikidataQ56210386 ScholiaQ56210386MaRDI QIDQ4705344

Michael Krivelevich, Noga Alon, Benjamin Sudakov

Publication date: 19 December 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

polynomial time algorithm spectral properties clique random graph probabilistic model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (52)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ Independent sets in semi-random hypergraphs ⋮ What Is Learned in Knowledge Graph Embeddings? ⋮ On independent sets in random graphs ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Information-theoretic thresholds from the cavity method ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ On combinatorial testing problems ⋮ Optimal detection of sparse principal components in high dimension ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ Random perturbation of low rank matrices: improving classical bounds ⋮ Community detection in sparse random networks ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers ⋮ Statistical and computational limits for sparse matrix detection ⋮ A Simple SVD Algorithm for Finding Hidden Partitions ⋮ Convex optimization for the planted \(k\)-disjoint-clique problem ⋮ Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Graph Partitioning via Adaptive Spectral Techniques ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ Finding a large submatrix of a Gaussian random matrix ⋮ Community Detection and Stochastic Block Models ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ Computational and statistical tradeoffs via convex relaxation ⋮ Unnamed Item ⋮ Nuclear norm minimization for the planted clique and biclique problems ⋮ Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time ⋮ Cliques in rank-1 random graphs: the role of inhomogeneity ⋮ Metastability in stochastic replicator dynamics ⋮ Robust exponential memory in Hopfield networks ⋮ Recovering the structure of random linear graphs ⋮ Community detection in dense random networks ⋮ Finding a planted clique by adaptive probing ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ Testing for Dense Subsets in a Graph via the Partition Function ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ The overlap gap property in principal submatrix recovery ⋮ Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Detecting positive correlations in a multivariate sample ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model ⋮ Heuristics for semirandom graph problems ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Do semidefinite relaxations solve sparse PCA up to the information limit?

This page was built for publication: