Source author record

Hans Raj Tiwary

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.CO Discrete Mathematics Computational Geometry quant-ph Formal Languages and Automata Theory

Catalog footprint

Research overview

9works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

It can be shown that each permutation group $G \sqsubseteq S_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, $S_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 \sqsubseteq S_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 \sqsubseteq S_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Δ)}\cdot m^{O(k)}$ . By combining our upper bound with a connection 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 Δ)}\cdot 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 $S_n$ we have that connected graphs of treewidth $o(n/\log n)$ and maximum degree $o(n/\log n)$ embedding subgroups of $S_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^{\varepsilon}$ for $\varepsilon<1$ and maximum degree $o(n/\log n)$ .

preprint2015arXiv

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

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.

preprint2015arXiv

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.

preprint2014arXiv

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).

preprint2014arXiv

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 Holevo's 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.

preprint2013arXiv

Extended formulations, non-negative factorizations and randomized communication protocols

An extended formulation of a polyhedron $P$ is a linear description of a polyhedron $Q$ together with a linear map $π$ such that $π(Q)=P$ . These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis' factorization theorem [M. Yannakakis. Expressing combinatorial optimization problems by linear programs. {\em J. Comput. System Sci.}, 43(3):441--466 (1991)] provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $P$ equals the nonnegative rank of its slack matrix $S$ . Moreover, Yannakakis also shows that the nonnegative rank of $S$ is at most $2^c$ , where $c$ is the complexity of any \emph{deterministic} protocol computing $S$ . In this paper, we show that the latter result can be strengthened when we allow protocols to be \emph{randomized}. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis' factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope $P$ equals the minimum complexity of a randomized communication protocol computing the slack matrix of $P$ in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

preprint2013arXiv

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

preprint2012arXiv

Extended formulations for polygons

The extension complexity of a polytope $P$ is the smallest integer $k$ such that $P$ is the projection of a polytope $Q$ with $k$ facets. We study the extension complexity of $n$ -gons in the plane. First, we give a new proof that the extension complexity of regular $n$ -gons is $O(\log n)$ , a result originating from work by Ben-Tal and Nemirovski (2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of $\sqrt{2n}$ on the extension complexity of generic $n$ -gons. Finally, we prove that there exist $n$ -gons whose vertices lie on a $O(n) \times O(n^2)$ integer grid with extension complexity $Ω(\sqrt{n}/\sqrt{\log n})$ .

preprint2012arXiv

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Hans Raj Tiwary

Research overview

Is this your work?

9 publications

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

On the H-Free Extension Complexity of the TSP

A generalization of extension complexity that captures $P$

Generalised probabilistic theories and conic extensions of polytopes

Extended formulations, non-negative factorizations and randomized communication protocols

On the extension complexity of combinatorial polytopes

Extended formulations for polygons

On Computing the Shadows and Slices of Polytopes

See the researcher in context

Building this map preview

Hans Raj Tiwary

Research overview

Is this your work?

9 publications

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

On the H-Free Extension Complexity of the TSP

A generalization of extension complexity that captures PPP

Generalised probabilistic theories and conic extensions of polytopes

Extended formulations, non-negative factorizations and randomized communication protocols

On the extension complexity of combinatorial polytopes

Extended formulations for polygons

On Computing the Shadows and Slices of Polytopes

See the researcher in context

Building this map preview

A generalization of extension complexity that captures $P$