Statistical algorithms and a lower bound for detecting planted cliques

DOI10.1145/3046674zbMATH Open1397.68085arXiv1201.1214OpenAlexW2607171573MaRDI QIDQ4640281FDOQ4640281

Authors: Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Ying Xiao, Santosh S. Vempala 

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory (Kearns, 1998). Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size $O(n^{1/2-delta})$ for any constant $delta>0$. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Full work available at URL: https://arxiv.org/abs/1201.1214

Recommendations

• Statistical algorithms and a lower bound for detecting planted cliques
• Finding a planted clique by adaptive probing
• Sum-of-squares Lower Bounds for Planted Clique
• On the complexity of random satisfiability problems with planted solutions
• On the complexity of random satisfiability problems with planted solutions (extended abstract)

zbMATH Keywords

learning theorylower boundsplanted cliquestatistical algorithmsstatistical dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (23)

• On the complexity of random satisfiability problems with planted solutions
• Algorithmic obstructions in the random number partitioning problem
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Computational barriers in minimax submatrix detection
• Tensor clustering with planted structures: statistical optimality and computational limits
• Finding a planted clique by adaptive probing
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Computational barriers to estimation from low-degree polynomials
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Bilu-Linial stability, certified algorithms and the independent set problem
• Estimation of Wasserstein distances in the spiked transport model
• Polynomial‐time universality and limitations of deep learning
• The overlap gap property in principal submatrix recovery
• Computational lower bounds for graphon estimation via low-degree polynomials
• Average-case complexity of tensor decomposition for low-degree polynomials
• Statistical query lower bounds for tensor PCA
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• Adversarial manifold estimation
• Statistical algorithms and a lower bound for detecting planted cliques

This page was built for publication: Statistical algorithms and a lower bound for detecting planted cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640281)