This is the first of two talks in which the speaker will discuss the development of the theory of Toeplitz matrices and determinants in response to questions arising in the analysis of the Ising model of statistical mechanics. The first talk will be largely historical and the second will describe the state of the art today, including recent results of the speaker and his colleagues Alexander Its and Igor Krasovsky.
We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are far from optimal. Previously the best known extractor for (n,k) sources requires O(log n/log k) independent sources [Rao06, Barak-Rao-Shaltiel-Wigderson06]. In this talk I will give a new extractor that uses only O(log (log n/log k))+O(1) independent sources. This improves the previous best result exponentially.
Associated to an abelian variety A/K is a Galois representation which describes the action of the absolute Galois group of K on the torsion points of A. In this talk, we shall describe how large the image of this representation can be (in terms of a number field K and the dimension of A). We achieve this by considering abelian varieties in families and then using a special variant of Hilbert's irreducibility theorem. Some results of Serre on the mod ell Galois image will also be reviewed. (This is joint work with David Zureick-Brown)
We develop a simple geometric variant of the Kabatiansky-Levenshtein approach to proving sphere packing density bounds. This variant gives a small improvement to the best bounds known in Euclidean space (from 1978) and an exponential improvement in hyperbolic space. Furthermore, we show how to achieve the same results via the Cohn-Elkies linear programming bounds, and we formulate a few problems in harmonic analysis that could lead to even better bounds. This is joint work with Yufei Zhao.
Several examples of Hamiltonian evolution equations for systems with infinitely many degrees of freedom are presented. It is sketched how these equations can be derived from some underlying quantum dynamics ("mean-field limit") and what kind of physics they describe.
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).