# Research

Here's a (very) brief summary of what I do.

I have worked mostly on some computational problems in the Theory of Polytopes. The areas that I am usually involved in are Computational Geometry, Linear Algebra and Discrete & Combinatorial Optimization to name a few. To give you a better understanding of the kind of research I do, here's a summary of some of the problems that I have worked on or am currently working on.

A friendly bit of warning: This page - being a summary - is intentionally written with a bit of technical sloppiness. Expect details to be hidden under weasel words. If you are interested in more details, you can always read my papers! Feel free to drop me a line if you are not sure which papers relate to which problems.

### Extended Formulations

Every polytope is a shadow of some simplex. A polytope $$Q$$ is called the linear extension or the extended formulation of a polytope $$P$$ if $$P$$ is a shadow of $$Q$$.

What is the minimum size (for some natural definitions of size) of any linear extension of a given polytope ?

This question produces many interesting connections between the minimum size of any linear extension, non-negative factorization of matrices and complexity of randomized communication protocols.

Generalizing to extensions that are not necessarily polytopes leads to similar connections between the size of SDP extensions, positive semi-definite factorization of matrices (Non-standard terminology; See the publications page!) and complexity of quantum communication protocols.

At present I am working on a number of related problems. Check out my publication page to get an idea!

The rest of the list is somewhat in a chronological order (oldest first), although I do get back once in a while to every problem in this list. This also means that this list consists entirely of problems that I haven't been able to solve or that still have unanswered questions. If you are interested in any of these problems, I would love to hear from you.

### Vertex Enumeration

Problem: Given a polytope described by it's facet defining inequalities enumerate all its vertices.
What we know: This problem is (essentially) equivalent to the problem of computing all facets of a polytope described by it's vertices. Worst case optimal algorithms exist for this problem but the worst case scenario requires an exponential time since a $$d$$-dimensional polytope with $$m$$ facets can have $$\displaystyle\Theta(m^{\left\lfloor\frac{d}{2}\right\rfloor})$$ vertices. Efficient output sensitive algorithm for this problem are not known. Neither are any hardness results.

I have worked on many problems that lie in the "periphery" of the Vertex Enumeration problem. Many approaches that I have tried end up requiring solving problems that turn out to be NP-hard or as hard as checking graph isomorphism. Some of these problems are as basic as computing the minkowski sum or the intersection of polytopes, or checking whether a polytope is self-dual.

For the general problem, we are pretty much in the dark. If I had to put a wager on it, I'd put my money on a graph-isomorphism completeness result. But it's a rather weak hunch and considering how some very clever people who have spent quite a bit of time on it have no strong opinion either way, I would probably not wager more than ten euros.

Problem: We say that a point $$p$$ illuminates a point $$q$$ on the boundary of a convex body $$P$$, if the half-ray from $$p$$ to $$q$$ enters the interior of $$P$$ immediately after passing $$q$$. The conjecture states that $$2^d$$ points are sufficient for illuminating the entire surface of $$P$$, where $$d$$ is the dimension of the ambient space.
What we know: Roughly speaking, smoothness on the boundary of a convex body help the conjecture so the most interesting case is for polytopes. Even in dimension three it is not known whether 8 light sources suffice. It is known that 16 points suffice.

There are a variety of results on special classes of polytopes but in general we only have very crude answers. If you are interested in reading more about the problem, I recommend starting with the Wikipedia article and following up the references.

My contribution to this problem amounts only to a rather obvious observation that the associated computational problem, where you want to check whether a facet-defined polytope is completely illuminated by a given set of light sources, is NP-hard.

I and Daniel Werner did however come up with a (wrong) proof that the Levi-Hadwiger conjecture is asymptotically true for polytopes. The only reason I mention this here is that Günter Rote could not find an error right away. If you have ever run your ideas by Günter, you know why that counts as a bragging right!

### Oja Depth

Given a finite set $$P$$ of points in $$\mathbb{R}^d$$ the Oja depth of a point $$p$$ w.r.t $$P$$ is defined as the sum of volumes (normalized w.r.t the volume of $$\text{conv}(P)$$) of all simplices containing $$p$$ and $$d$$ other points from $$P$$. The Oja depth of the point set $$P$$ is defined as the minimum Oja depth of any point w.r.t $$P$$.

Problem: What is the worst case Oja depth of any point set?
What we know: The worst case Oja depth is conjectured to be $$(\frac{n}{d+1})^d$$. If true this bound is optimal since a point set consisting of $$\frac{n}{d+1}$$ points near each vertex of a simplex achieves this bound.

We know that the conjecture is true in the plane. We also know that for the general $$d$$ the Oja depth of any point set is at most $$\frac{2n^{d}}{2^{d}d!} - \frac{2d}{(d+1)^2(d+1)!} {n \choose d} + O(n^{d-1})$$.