Algorithms approaching the threshold for semi-random planted clique

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