scientific article; zbMATH DE number 1380608
From MaRDI portal
Publication:4705344
DOI<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.05082MaRDI QIDQ4705344
Michael Krivelevich, Noga Alon, Benjamin Sudakov
Publication date: 19 December 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
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:
