Algorithms approaching the threshold for semi-random planted clique
From MaRDI portal
Cites work
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A New Algorithm for the Robust Semi-random Independent Set Problem
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Coloring Random and Semi-Random k-Colorable Graphs
- Computational barriers to estimation from low-degree polynomials
- Expected complexity of graph partitioning problems
- Finding and certifying a large hidden clique in a semirandom graph
- Hardness of approximation
- Heuristics for semirandom graph problems
- How robust are reconstruction thresholds for community detection?
- scientific article; zbMATH DE number 1303602 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Introduction to Semirandom Models
- Large Cliques Elude the Metropolis Process
- Learning from untrusted data
- Linear degree extractors and the inapproximability of max clique and chromatic number
- List Decodable Learning via Sum of Squares
- Mixture models, robustness, and sum of squares proofs
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On the integrality gap of degree-4 sum of squares for planted clique
- Optimal low-degree hardness of maximum independent set
- Reducibility among combinatorial problems
- Robust linear regression: optimal rates in polynomial time
- Robust moment estimation and improved clustering via sum of squares
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Semialgebraic Proofs and Efficient Algorithm Design
- Semidefinite programs on sparse random graphs and their application to community detection
- Settling the robust learnability of mixtures of Gaussians
- Statistical algorithms and a lower bound for detecting planted cliques
- Subexponential algorithms for unique games and related problems
- Sum of squares lower bounds for refuting any CSP
- Sum-of-squares proofs and the quest toward optimal algorithms
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
Cited in
(4)
This page was built for publication: Algorithms approaching the threshold for semi-random planted clique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499350)
