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.

Levi-Hadwiger Illumination Conjecture

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