Statistical algorithms and a lower bound for detecting planted cliques
From MaRDI portal
Publication:5495836
DOI10.1145/2488608.2488692zbMath1293.68142OpenAlexW2065563937MaRDI QIDQ5495836
Vitaly Feldman, Elena Grigorescu, Y. Xiao, Lev Reyzin, Santosh Vempala
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488692
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On the Power of Learning from k-Wise Queries ⋮ Optimal detection of sparse principal components in high dimension ⋮ A simple spectral algorithm for recovering planted partitions ⋮ Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time ⋮ Statistical and computational limits for sparse matrix detection ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ Optimal testing for planted satisfiability problems ⋮ Unnamed Item ⋮ On the hardness of designing public signals ⋮ Community detection in dense random networks ⋮ Statistical active learning algorithms for noise tolerance and differential privacy ⋮ Computational barriers in minimax submatrix detection
