Speaker - Mateus de Oliveira Oliveira

On Grammars, Polytopes, and Groups Fri, Nov 8, 2019 12:30 CET

Speakers: Mateus de Oliveira Oliveira

A fundamental step towards solving combinatorial problems using techniques from linear programming theory is to encode the space of feasible solutions for such problems as the set of vertices of polytopes of small extension complexity. In this work, we establish several connections between the extension complexity of polytopes, formal language theory, and group theory. In particular, we introduce the notion of homogeneous context-free grammars and show that polytopes corresponding to languages accepted by polynomial-size non-uniform families of grammars with polynomial homogeneity have polynomial extension complexity.