Sum of Squares Lower Bounds from Pairwise Independence

DOI10.1145/2746539.2746625zbMath1321.68295arXiv1501.00734OpenAlexW2028085501MaRDI QIDQ2941493

Siu-On Chan, Pravesh K. Kothari, Boaz Barak

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.00734

zbMATH Keywords

pairwise independencelower boundsconstraint satisfactionsum of squares hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Cryptographic hardness of random local functions. Survey ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Unnamed Item ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Sum of Squares Lower Bounds from Pairwise Independence