An information complexity approach to extended formulations

DOI10.1145/2488608.2488629zbMath1293.68137OpenAlexW2091039687MaRDI QIDQ5495786

Mark Braverman, Ankur Moitra

Publication date: 7 August 2014

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

Full work available at URL: https://doi.org/10.1145/2488608.2488629

zbMATH Keywords

communication complexityextended formulationsnon-negative rank

Mathematics Subject Classification ID

Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (28)

Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Common information and unique disjointness ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Certifying equality with limited interaction ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ The matching problem has no small symmetric SDP ⋮ Communication complexity with small advantage ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Extension Complexity of Independent Set Polytopes ⋮ Affine reductions for LPs and SDPs ⋮ A note on the extension complexity of the knapsack polytope ⋮ Information lower bounds via self-reducibility ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Extended formulations for vertex cover ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ On the existence of 0/1 polytopes with high semidefinite extension complexity ⋮ Uncapacitated flow-based extended formulations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Worst-case analysis of clique MIPs ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity ⋮ Approximate cone factorizations and lifts of polytopes ⋮ On the streaming indistinguishability of a random permutation and a random function

This page was built for publication: An information complexity approach to extended formulations