Extension complexity of formal languages
From MaRDI portal
Publication:778518
DOI10.1007/s00224-019-09951-xzbMath1446.68083arXiv1603.07786OpenAlexW2988591986WikidataQ126864363 ScholiaQ126864363MaRDI QIDQ778518
Publication date: 2 July 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.07786
Cites Work
- Unnamed Item
- Unnamed Item
- The projected faces property and polyhedral relations
- Weak and strong one-way space complexity classes
- Streaming algorithms for language recognition problems
- Some efficiently solvable problems over integer partition polytopes
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- On the extension complexity of combinatorial polytopes
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- Disjunctive programming: Properties of the convex hull of feasible points
- Tutorials on emerging methodologies and applications in operations research. Selected papers presented at INFORMS 2004, Denver, CO, USA, October 24--27, 2004.
- Information-theoretic approximations of the nonnegative rank
- Some \(0/1\) polytopes need exponential size extended formulations
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Lectures on Polytopes
- The Matching Polytope has Exponential Extension Complexity
- Computational Complexity
- Extended formulations in combinatorial optimization
This page was built for publication: Extension complexity of formal languages
