Georgia Institute of Technology College of Sciences

We present algorithms for performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Our interpolation algorithms use as a substep an algorithm that originally is by R. Prony from the French Revolution (Year III, 1795) for interpolating exponential sums and which is rediscovered to decode digital error correcting BCH codes over finite fields (1960). Since Prony's algorithm is quite simple, we will give a complete description, as an alternative for Lagrange/Newton interpolation for sparse polynomials. When very few errors in the evaluations are permitted, multiple sparse interpolants are possible over finite fields or the complex numbers, but not over the real numbers. The problem is then a simple example of list-decoding in the sense of Guruswami-Sudan. Finally, we present a connection to the Erdoes-Turan Conjecture (Szemeredi's Theorem). This is joint work with Clement Pernet, Univ. Grenoble.

Estimation of the covariance matrix has attracted significant attention of the statistical research community over the years, partially due to important applications such as Principal Component Analysis. However, frequently used empirical covariance estimator (and its modifications) is very sensitive to outliers, or ``atypical’’ points in the sample. As P. Huber wrote in 1964, “...This raises a question which could have been asked already by Gauss, but which was, as far as I know, only raised a few years ago (notably by Tukey): what happens if the true distribution deviates slightly from the assumed normal one? As is now well known, the sample mean then may have a catastrophically bad performance…” Motivated by Tukey's question, we develop a new estimator of the (element-wise) mean of a random matrix, which includes covariance estimation problem as a special case. Assuming that the entries of a matrix possess only finite second moment, this new estimator admits sub-Gaussian or sub-exponential concentration around the unknown mean in the operator norm. We will present extensions of our approach to matrix-valued U-statistics, as well as applications such as the matrix completion problem. Part of the talk will be based on a joint work with Xiaohan Wei.

In this talk we will discuss several ways to construct new convex bodies out of old ones. We will start by defining various methods of "averaging" convex bodies, both old and new. We will explain the relationships between the various definitions and their connections to basic conjectures in convex geometry. We will then discuss the power operation, and explain for example why every convex body has a square root, but not every convex body has a square. If time permits, we will briefly discuss more complicated constructions such as logarithms. The talk is based on joint work with Vitali Milman.

Every graph G has canonically associated to a finite abelian group called the Jacobian group. The cardinality of this group is the number of spanning trees in G. If G is planar, the Jacobian group admits a natural simply transitive action on the set of spanning trees. More generally, for any graph G one can define a whole family of (non-canonical) simply transitive group actions. The analysis of such group actions involves ideas from tropical geometry. Part of this talk is based on joint work with Yao Wang, and part is based on joint work with Spencer Backman and Chi Ho Yuen.