Prof. Dr. Laura Sanita (University of Waterloo, Canada)
On the hardness of computing the diameter of a polytope abstract
Abstract:
The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on 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 Algorithm for solving Linear Programs.
The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, Frieze and Teng in 1994 showed that computing the diameter of a polytope is weakly NP-hard.
In this talk, I will show that their hardness result can be significantly strengthened, by exploiting the structure of a notorious and well-studied polytope in the optimization community: the fractional matching polytope. In particular, I will give an exact characterization of the diameter of this polytope, and then use it to derive strong NP-hardness (in fact, APX-hardness) for the problem of computing the diameter. Eventually, I will also show that the structure of the fractional matching polytope can be used to prove new hardness results regarding a generalized notion of diameter, called circuit-diameter, that has recently gained a lot of attention in the literature.
10:00 • EPF Lausanne, MA B1 11
Jiyeon Moon (Ajou University, Suwon, Korea)
Wedge operation on toric manifolds with Picard number 4 abstract
Abstract:
In this talk, we will discuss toric manifolds over the simplicial complex obtained by finitely many wedges on the dual complex of the 3-cube with one vertex cut. We will explain why this is important in the classification problem in toric topology. This is work jointly with Suyong Choi and Hanchul Park.
14:00 • Université de Neuchâtel, Institut de Mathématiques, Rue Emile Argand 14, B 217
Dr. Ilya Khayutin (Princeton University, New Jersey)
Arithmetic and dynamics on homogeneous spaces abstract
Abstract:
Arithmetic homogeneous spaces and their quotients are ubiquitous in number theory. All-important examples are the modular curve, more general Shimura varieties, and the space of lattices in the Euclidean space of a fixed dimension. In this talk we will discuss questions about equidistribution of arithmetic objects on homogeneous spaces. These objects often arise as periodic orbits of actions by an algebraic group. Some of the most interesting actions on homogeneous spaces, from an arithmetic point of view, are those of diagonalizable groups, viz. algebraic tori. They are related, inter alia, to Galois orbits of special points on Shimura varieties, such as the Heegner points on the modular curve. These actions also generalize the geodesic flow on a hyperbolic manifold.
The orbits of diagonalizable group actions on homogeneous spaces remain mysterious. I will review several outstanding questions about equidistribution of periodic orbits for higher rank diagonalizable groups and some major challenges they pose. I will then discuss recent progress based on a fusion of ideas from homogeneous dynamics, arithmetic and automorphic forms.
15:00 • EPF Lausanne, MA B1 11