It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can be embedded in the n-clique K_n, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group G⊑ 𝕊_n can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group G ⊑ 𝕊_n that can be embedded into a connected graph with m vertices, treewidth k, and maximum degree Δ, can also be generated by a context-free grammar of size 2^{O(kΔlogΔ)}⋅ m^{O(k)}. By combining our upper bound with a connection established by Pesant, Quimper, Rousseau and Sellmann [Gilles Pesant et al., 2009] between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity 2^{O(kΔlogΔ)}⋅ m^{O(k)}. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated 2^{Ω(n)} lower bound on the grammar complexity of the symmetric group 𝕊_n due to Glaister and Shallit [Glaister and Shallit, 1996] we have that connected graphs of treewidth o(n/log n) and maximum degree o(n/log n) embedding subgroups of 𝕊_n of index 2^{cn} for some small constant c must have n^{ω(1)} vertices. This lower bound can be improved to exponential on graphs of treewidth n^{ε} for ε < 1 and maximum degree o(n/log n).

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

We study several canonical decision problems arising from some well-known theorems from combinatorial geometry. Among others, we show that computing the minimum size of a Caratheodory set and a Helly set and certain decision versions of the hs cut problem are W[1]-hard (and NP-hard) if the dimension is part of the input. This is done by fpt-reductions (which are actually ptime-reductions) from the d-Sum problem. Our reductions also imply that the problems we consider cannot be solved in time n^{o(d)} (where n is the size of the input), unless the Exponential-Time Hypothesis (ETH) is false. The technique of embedding d-Sum into a geometric setting is conceptually much simpler than direct fpt-reductions from purely combinatorial W[1]-hard problems (like the clique problem) and has great potential to show (parameterized) hardness and (conditional) lower bounds for many other problems.

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complexity of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.

For polytopes P,Q ⊂ Rd we consider the intersection P ∪ Q; the convex hull of the union CH(P ∪ Q); and the Minkowski sum P+Q. We prove that given rational H-polytopes P1,P2,Q it is impossible to verify in polynomial time whether Q=P1+P2, unless P=NP. In particular, this shows that there is no output sensitive polynomial algorithm to compute the facets of the Minkowski sum of two arbitrary H-polytopes even if we consider only rational polytopes. Since the convex hull of the union and the intersection of two polytopes relate naturally to the Minkowski sum via the Cayley trick and polarity, similar hardness results follow for these operations as well.