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