Subsampling mathematical relaxations and average-case complexity

MaRDI QIDQ5365060zbMATH OpenFDO

Authors Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133077

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
• Fast SDP algorithms for constraint satisfaction problems
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs

Cited in

(11)

• Asymptotic relative submajorization of multiple-state boxes
• Subquadratic SNARGs in the random oracle model
• On the hardness of finding subsets with equal average
• On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
• On percolation and \(\mathcal{NP}\)-hardness
• Sublinear algorithms for MAXCUT and correlation clustering
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• Sherali-adams strikes back
• Amplification and Derandomization without Slowdown
• Local and global expansion in random geometric graphs
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT

This page was built for publication: Subsampling mathematical relaxations and average-case complexity

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