Algorithms approaching the threshold for semi-random planted clique
From MaRDI portal
Publication:6499350
DOI10.1145/3564246.3585184MaRDI QIDQ6499350
Pravesh K. Kothari, Rares-Darius Buhai, David Steurer
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Expected complexity of graph partitioning problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Heuristics for semirandom graph problems
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- Optimal low-degree hardness of maximum independent set
- Computational barriers to estimation from low-degree polynomials
- Subexponential Algorithms for Unique Games and Related Problems
- Large Cliques Elude the Metropolis Process
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
- Sum-of-squares proofs and the quest toward optimal algorithms
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Coloring Random and Semi-Random k-Colorable Graphs
- Finding and certifying a large hidden clique in a semirandom graph
- Learning from untrusted data
- Sum of squares lower bounds for refuting any CSP
- Reducibility among Combinatorial Problems
- Introduction to Semirandom Models
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- List Decodable Learning via Sum of Squares
- A New Algorithm for the Robust Semi-random Independent Set Problem
- Semialgebraic Proofs and Efficient Algorithm Design
- Mixture models, robustness, and sum of squares proofs
- Robust moment estimation and improved clustering via sum of squares
- Semidefinite programs on sparse random graphs and their application to community detection
- How robust are reconstruction thresholds for community detection?
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Statistical algorithms and a lower bound for detecting planted cliques
- Robust linear regression: optimal rates in polynomial time
- Settling the robust learnability of mixtures of Gaussians
This page was built for publication: Algorithms approaching the threshold for semi-random planted clique