Detection of dense subhypergraphs by low-degree polynomials
From MaRDI portal
Cites work
- A nearly tight sum-of-squares lower bound for the planted clique problem
- Community detection in dense random networks
- Community detection in sparse random networks
- Computational barriers in minimax submatrix detection
- Computational barriers to estimation from low-degree polynomials
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Efficient Bayesian estimation from few samples: community detection and related problems
- Finding one community in a sparse graph
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 3564899 (Why is no real title available?)
- scientific article; zbMATH DE number 7650426 (Why is no real title available?)
- scientific article; zbMATH DE number 7788417 (Why is no real title available?)
- Information Limits for Detecting a Subhypergraph
- Information Limits for Recovering a Hidden Community
- Large Cliques Elude the Metropolis Process
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- Pseudorandom generators with long stretch and low locality from random local one-way functions
- Sharp detection boundaries on testing dense subhypergraph
- Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
- Strictly balanced uniform hypergraphs and generalizations of zero-one law
- Strongly balanced graphs and random graphs
- Sum-of-squares lower bounds for densest k-subgraph
- Tensor clustering with planted structures: statistical optimality and computational limits
- The densest k-subhypergraph problem
- The power of sum-of-squares for detecting hidden structures
Cited in
(5)- The low-degree hardness of finding large independent sets in sparse random hypergraphs
- A computational transition for detecting correlated stochastic block models by low-degree polynomials
- Low-degree hardness of detection for correlated Erdős-Rényi graphs
- Counting stars is constant-degree optimal for detecting any planted subgraph
- Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
This page was built for publication: Detection of dense subhypergraphs by low-degree polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7027462)
