An information complexity approach to extended formulations

DOI10.1145/2488608.2488629MaRDI QIDQ5495786zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Ankur Moitra

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

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

Recommendations

• scientific article; zbMATH DE number 3922389
• scientific article; zbMATH DE number 3516928
• scientific article; zbMATH DE number 3508265
• Information-based complexity of linear operator equations
• Information geometric methods for complexity
• Information complexity of weakly singular integral equations
• A circuit complexity formulation of algorithmic information theory
• A new method for compact extension of information algebras
• scientific article; zbMATH DE number 4201689
• scientific article; zbMATH DE number 5583062

Cited in

(31)

• Extensive form implementation in incomplete information environments
• The matching problem has no small symmetric SDP
• Affine reductions for LPs and SDPs
• Extended formulations for vertex cover
• Worst-case analysis of clique MIPs
• Trading information complexity for error. II: The case of a large error and the external information complexity
• On the streaming indistinguishability of a random permutation and a random function
• Communication complexity with small advantage
• Approximate cone factorizations and lifts of polytopes
• A note on the extension complexity of the knapsack polytope
• Exponential lower bounds for polytopes in combinatorial optimization
• 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
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Average case polyhedral complexity of the maximum stable set problem
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Extension complexity of independent set polytopes
• Information lower bounds via self-reducibility
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• An almost optimal algorithm for computing nonnegative rank
• The communication complexity of set intersection and multiple equality testing
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Complex psd-minimal polytopes in dimensions two and three
• The work of Mark Braverman
• Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
• Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Uncapacitated flow-based extended formulations

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

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