Extension complexity of formal languages
From MaRDI portal
Publication:778518
DOI10.1007/S00224-019-09951-XzbMATH Open1446.68083arXiv1603.07786OpenAlexW2988591986WikidataQ126864363 ScholiaQ126864363MaRDI QIDQ778518FDOQ778518
Authors: Hans Raj Tiwary 
Publication date: 2 July 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Abstract: In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of formal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Full work available at URL: https://arxiv.org/abs/1603.07786
Recommendations
Cites Work
- Lectures on Polytopes
- Computational Complexity
- The projected faces property and polyhedral relations
- Title not available (Why is that?)
- Disjunctive programming: Properties of the convex hull of feasible points
- Weak and strong one-way space complexity classes
- Title not available (Why is that?)
- Some \(0/1\) polytopes need exponential size extended formulations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Extended formulations in combinatorial optimization
- Information-theoretic approximations of the nonnegative rank
- Exponential lower bounds for polytopes in combinatorial optimization
- Lower bounds on the size of semidefinite programming relaxations
- Streaming algorithms for language recognition problems
- Some efficiently solvable problems over integer partition polytopes
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- Tutorials on emerging methodologies and applications in operations research. Selected papers presented at INFORMS 2004, Denver, CO, USA, October 24--27, 2004.
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
Cited In (4)
This page was built for publication: Extension complexity of formal languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778518)
