Sum-of-squares lower bounds for densest k-subgraph

Cites Work

The quadratic knapsack problem -- a survey
Convex optimization for the densest subgraph and densest submatrix problems
Relations between average case complexity and approximation complexity
Reducibility among combinatorial problems
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
Global optimization with polynomials and the problem of moments
Approximation algorithms for maximization problems arising in graph partitioning
Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
The Hospitals/Residents Problem with Quota Lower Bounds
Expander flows, geometric embeddings and graph partitioning
The dense \(k\)-subgraph problem
Complexity of finding dense subgraphs
Title not available (Why is that?)
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Expander flows, geometric embeddings and graph partitioning
Approximate Constraint Satisfaction Requires Large LP Relaxations
Integrality gaps for Sherali-Adams relaxations
Public-key cryptography from different assumptions
Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
Graph expansion and the unique games conjecture
Finding a collective set of items: from proportional multirepresentation to group recommendation
Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
Lower bounds on the size of semidefinite programming relaxations
Title not available (Why is that?)
An approach to obtaining global extremums in polynomial mathematical programming problems
Title not available (Why is that?)
The densest \(k\)-subhypergraph problem
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
Finding Dense Subgraphs with Size Bounds
Partially ordered knapsack and applications to scheduling
Approximating dense MAX 2-CSPs
On the approximability of the minimum rainbow subgraph problem and other related problems
Approximating Minimum-Power Degree and Connectivity Problems
Improved approximation algorithms for label cover problems
The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
Bounds on the norms of uniform low degree graph matrices
Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
CSP gaps and reductions in the lasserre hierarchy
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Integrality gaps for sparsest cut and minimum linear arrangement problems
Semialgebraic Proofs and Efficient Algorithm Design
Traffic-light scheduling on the grid
Complexity of Positivstellensatz proofs for the knapsack
Sum of squares lower bounds for refuting any CSP
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Sum-of-squares Lower Bounds for Planted Clique
SOS is not obviously automatizable, even approximately
Partitioning a graph into small pieces with applications to path transversal
Approximation algorithms and hardness of the \(k\)-route cut problem
Hardness and approximation for network flow interdiction
Settling the robust learnability of mixtures of Gaussians
On the bit complexity of sum-of-squares proofs
Mean estimation with sub-Gaussian rates in polynomial time
Robust moment estimation and improved clustering via sum of squares
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Robust linear regression: optimal rates in polynomial time
Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Minimizing the union: tight approximations for small set bipartite vertex expansion
Approximation algorithms for label cover and the log-density threshold
Sherali-Adams integrality gaps matching the log-density threshold
On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
Computational barriers to estimation from low-degree polynomials
Mixture models, robustness, and sum of squares proofs
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
ETH hardness for densest-\(k\)-subgraph with perfect completeness
The complexity of the simultaneous cluster problem
On the integrality gap of degree-4 sum of squares for planted clique
SOS lower bound for exact planted clique
Playing unique games on certified small-set expanders
Dense subgraph problems with output-density conditions
Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model

This page was built for publication: Sum-of-squares lower bounds for densest \(k\)-subgraph

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