Events

In this talk I will discuss how semidefinite programming can be used to
compute bounds in discrete geometry. First I will focus on compact problems
such as the spherical code problem, which asks for the largest number of
points on a unit sphere such that the inner product between any pair of
disctinct points is at most some given constant. Then I will discuss the
(noncompact) sphere packing problem, explain how this connects to problems
in analytic number theory and the conformal bootstrap program, and discuss
how semidefinite programming can be used to obtain improved bounds.

The diameter of a polytope P is the maximum length of a shortest path
between a pair of vertices of P, when one is allowed to walk on the
edges (1-dimensional faces) of P. Despite decades of studies, it is
still not known whether the diameter of a d-dimensional polytope with n
facets can be bounded by a polynomial function of n and d. This is a
fundamental open question in discrete mathematics, motivated by the
(still unknown) existence of a polynomial pivot rule for the Simplex
method for solving Linear Programs.
A generalized notion of diameter, recently introduced in the
literature, is that of circuit-diameter, defined as the maximum length
of a shortest path between two vertices of P, where the path can use
all edge directions (called circuits) that can arise by translating
some of the facets of P.
In this talk, I will discuss some algorithmic and complexity results
related to the diameter and the circuit-diameter of polytopes,
highlighting important open questions.