On the H-Free Extension Complexity of the TSP

It is known that the extension complexity of the TSP polytope for the complete graph $K_n$ is exponential in $n$ even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets $mathcal{H}$ of facet-defining inequalities of the TSP polytope. In particular, we consider the case when $mathcal{H}$ is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called $(h,t)$-uniform inequalities, which may be of independent interest.

Polynomial size linear programs for problems in P

A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex disjoint edges from $E$ that include all vertices in $V$. The perfect matching problem is to decide if $G$ has such a matching. Recently Rothvo{ss} proved the striking result that the Edmonds matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {bf P/Poly}.

A generalization of extension complexity that captures $P$

In this paper we propose a generalization of the extension complexity of a polyhedron $Q$. On the one hand it is general enough so that all problems in $P$ can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for $NP$-hard problems independently of whether or not $P=NP$. The generalization, called $H$-free extension complexity, allows for a set of valid inequalities $H$ to be excluded in computing the extension complexity of $Q$. We give results on the $H$-free extension complexity of hard matching problems (when $H$ are the odd set inequalities) and the traveling salesman problem (when $H$ are the subtour elimination constraints).

Generalised probabilistic theories and conic extensions of polytopes

Generalized probabilistic theories (GPT) provide a general framework that includes classical and quantum theories. It is described by a cone $C$ and its dual $C^*$. We show that whether some one-way communication complexity problems can be solved within a GPT is equivalent to the recently introduced cone factorisation of the corresponding communication matrix $M$. We also prove an analogue of Holevos theorem: when the cone $C$ is contained in $mathbb{R}^{n}$, the classical capacity of the channel realised by sending GPT states and measuring them is bounded by $log n$. Polytopes and optimising functions over polytopes arise in many areas of discrete mathematics. A conic extension of a polytope is the intersection of a cone $C$ with an affine subspace whose projection onto the original space yields the desired polytope. Extensions of polytopes can sometimes be much simpler geometric objects than the polytope itself. The existence of a conic extension of a polytope is equivalent to that of a cone factorisation of the slack matrix of the polytope, on the same cone. We show that all $0/1$ polytopes whose vertices can be recognized by a polynomial size circuit, which includes as a special case the travelling salesman polytope and many other polytopes from combinatorial optimisation, have small conic extension complexity when the cone is the completely positive cone. Using recent exponential lower bounds on the linear extension complexity of polytopes, this provides an exponential gap between the communication complexity of GPT based on the completely positive cone and classical communication complexity, and a conjectured exponential gap with quantum communication complexity. Our work thus relates the communication complexity of generalisations of quantum theory to questions of mainstream interest in the area of combinatorial optimisation.

On Computing the Shadows and Slices of Polytopes

We study the complexity of computing the projection of an arbitrary $d$-polytope along $k$ orthogonal vectors for various input and output forms. We show that if $d$ and $k$ are part of the input (i.e. not a constant) and we are interested in output-sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are in some sense non-degenerate. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable linear subspace and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. To compare the complexity of projection and vertex enumeration, we define new complexity classes based on the complexity of Vertex Enumeration.

On Computing the Vertex Centroid of a Polyhedron

Let $mathcal{P}$ be an $mathcal{H}$-polytope in $mathbb{R}^d$ with vertex set $V$. The vertex centroid is defined as the average of the vertices in $V$. We prove that computing the vertex centroid of an $mathcal{H}$-polytope is #P-hard. Moreover, we show that even just checking whether the vertex centroid lies in a given halfspace is already #P-hard for $mathcal{H}$-polytopes. We also consider the problem of approximating the vertex centroid by finding a point within an $epsilon$ distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an $mathcal{H}$-polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to emph{any} ``sufficiently non-trivial (for example constant) distance, can be used to construct a fully polynomial approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of $d^{{1/2}-delta}$ for any fixed constant $delta>0$.