Mathematics of Information
4:00-5:00 pm in Annenberg 314
(except where otherwise noted)
October 2, 2018
Ben Lee Volk
Algebraic Complexity Theory: Lower bounds and Derandomization (1st of 2 parts)
Algebraic Complexity theory is a subfield of complexity theory, studying computational problems of algebraic flavor such as multiplying matrices, computing the determinant, and more generally, computing polynomials over a field, where the complexity is measured by the number of algebraic operations needed to compute it.
Two basic open problems in the area are (1) proving superpolynomial circuit lower bounds for explicit polynomials (which is the algebraic analog to the P vs. NP problem), and (2) designing deterministic efficient algorithms for the Polynomial Identity Testing problem, that asks to determine, given a circuit computing a polynomial, whether it computes the zero polynomial.
Studying these questions often leads to beautiful mathematical questions of combinatorial, algebraic and geometric nature.
In this talk, we will discuss several old and new results in the area, explore the mysterious, bidirectional and intricate connections between the two problems above, and give some open problems.
October 9, 2018
Ben Lee Volk
Algebraic Complexity Theory: Lower bounds and Derandomization (2nd of 2 parts)
October 16, 2018
Hard-core interactions on graphs
In this talk I will introduce the hard-core model with Metropolis transition probabilities on finite graphs and its multi-state generalization. Motivated by the study of random-access networks performance, I will focus on the low-temperature regime and study the asymptotic behavior of these interacting particle systems by looking at first hitting times between stable states and mixing times. In particular, I will show how the order-of-magnitude of these hitting and mixing times depends on the underlying graph structure and derive precise asymptotics for various regular lattices. These results have been obtained extending the so-called "pathwise approach" developed in the statistical physics literature to study metastability phenomena and yielded a rigorous understanding of the root cause for poor delay performance of random-access networks.
October 23, 2018
Alessandro Achille (UCLA)
Complexity, Noise, and Emergent Properties of Learning Deep Representations
I will show that Information Theoretic quantities control and describe a large part of the training process of Deep Neural Networks, and can be used to explain how properties, such as invariance to nuisance variability and disentanglement of semantic factors, emerge naturally in the learned representation. The resulting theory has connections with several fields ranging from algorithmic complexity to variational inference. This framework not only predicts the asymptotic behavior of deep networks, but also shows that the initial learning transient has a large irreversible effect on the outcome of the training, which gives rise to critical learning periods akin to those observed in biological systems. This urges us to study the complex, and so far neglected, initial phase of learning.
October 30, 2018
Combining and Comparing Experiments
A classical statistical model of hypothesis testing is the Blackwell Le Cam experiment, in which an observer makes inferences regarding the veracity of an hypothesis by observing a random outcome whose distribution depends on whether or not the hypothesis holds. We address a number of natural, classical questions: when does one experiment have more information than another? How can we quantify the amount of information an experiment holds? Our results include an answer to an old question of Blackwell, as well as a novel axiomatization of Kullback-Leibler divergence.
Joint with Xiaosheng Mu, Luciano Pomatto and Philipp Strack
November 27, 2018
Approximate Gaussian Elimination for Laplacians
We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian matrix by a sparse LU factorization. We compute this factorization by subsampling standard Gaussian elimination. This gives the simplest known nearly linear time solver for Laplacian equations. The crux of our proof is the use of matrix martingales to analyze the algorithm. Finally, we will take a look at ongoing efforts to implement robust and fast Laplacian solvers based on these ideas.
Based on joint work with Sushant Sachdeva and Daniel Spielman.
December 4, 2018
Jan Hazla (MIT)
CMI Faculty Lunches
November 8, 2018
Newton Polytopes and Relative Entropy Optimization
We discuss how relative entropy is uniquely suited to optimization problems involving sparse polynomials. Our results connect to the work of Descartes (the rule of signs) and Khovanskii (the theory of fewnomials). The Newton polytope associated to a polynomial plays a central role in our development. This is joint work with Riley Murray and Adam Wierman.
December 13, 2018
January 10, 2019
February 14, 2019
March 14, 2019
April 11, 2019
May 9, 2019
June 13, 2019