Georgia Institute of Technology College of Sciences

We prove a quantitative Brunn-Minkowski inequality for sets E and K,one of which, K, is assumed convex, but without assumption on the other set. We are primarily interested in the case in which K is a ball. We use this to prove an estimate on the remainder in the Riesz rearrangement inequality under certain conditions on the three functions involved that are relevant to a problem arising in statistical mechanics: This is joint work with Franceso Maggi.

Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O(\sqrt{n})) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations. In this talk, for center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1+\sqrt{2})-factor perturbations, solving an open problem of Awasthi et al. For k-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small fraction of the points after perturbation. We give the first bounds known for k-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering which is a generally much harder objective than center-based objectives. Our algorithms are based on new linkage criteria that may be of independent interest.

This talk deals with problems that are asymptotically related to best-packing and best-covering. In particular, we discuss how to efficiently generate N points on a d-dimensional manifold that have the desirable qualities of well-separation and optimal order covering radius, while asymptotically having a prescribed distribution. Even for certain small numbers of points like N=5, optimal arrangements with regard to energy and polarization can be a challenging problem.

In dynamical systems, the long term behavior is organized by invariant manifolds that serve as landmarks that organize the traffic. There are two main theorems (established around 40-60 years ago) that tell you that these manifolds persist under small perturbations: KAM theorem and the theory of normally hyperbolic manifolds. In recent times there have been constructive proofs of these results which also lead to effective algorithms which allow to explore what happens in the border of the applicability of the theorems. We plan to review the basic concepts and present the experimental results.