## Günter Rote:

# The algebraic conspiracy

In: *Oberwolfach Reports*, Vol. 14, European Mathematical Society -
Publishing House, 2017, pp. 1180–1182.
doi:10.4171/OWR/2017/19*
* →BibTeX
### Abstract

We consider the problem of sandwiching a polytope `Δ`
with a given number `k` of vertices between two nested polytopes
`P` and `Q` in `d` dimensions. The polytope
`P` is not necessarily full-dimensional.

Besides the question of (a) computing `Δ`, we study
the following question: (b) Assuming that the given polytopes `P`
and `Q` are rational polytopes (polytopes with rational vertex
coordinates), does it suffice to look for `Δ` among the
rational polytopes?

This problem has several applications: (1) When `Q` is a dilation of
`P` (or an offset of `P`), `Δ` can
serve as a thrifty approximation of `P`. (2) The polytope nesting
problem can model the nonnegative rank of a matrix, and thereby the extension
complexity of polytopes, as well as other problems in statistics and
communication complexity. It was in this context that question (b) was
first asked.

Last update: June 5, 2018.