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

Cites work

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

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)