Mathematics of Information Seminar (CS286)
4:005:00 pm in Annenberg 314 (except where otherwise noted)
October 1, 2019
Jingcheng Liu
Approximate counting, phase transitions & geometry of polynomials
In classical statistical physics, a phase transition is understood by studying the geometry (the zeroset) of an associated polynomial (the partition function). In this talk I will show that one can exploit this notion of phase transitions algorithmically, and conversely exploit the analysis of algorithms to understand phase transitions.
As applications, I will give efficient deterministic approximation algorithms (FPTAS) for counting qcolorings, and for computing the partition function of the Ising model.
This talk is fully selfcontained, and based on joint work with Alistair Sinclair and Piyush Srivastava.
October 8, 2019
Jingcheng Liu
Uniform Sampling Through the Lovász Local Lemma
We propose a new algorithmic framework, called partial rejection sampling, to draw samples exactly from a product distribution conditioned on avoiding a set of bad events. Our framework builds new connections between the variable framework of the Lovász Local Lemma and some classical sampling algorithms such as the cyclepopping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample (weighted) independent sets, and satisfying assignments of kCNF formulas with bounded variable occurrences.
Based on joint work with Heng Guo and Mark Jerrum.
October 15, 2019
Grigory Yaroslavtsev
Advances in Linear Sketching over Finite Fields
I will describe recent advances in linear sketching over finite fields and its relationship to logrank conjecture and (quantum) communication complexity. For a function f: Z_p^n > R a linear sketch modulo p is a distribution A over k x n matrices with entries in Z_p which for every x \in Z_p^n allows one to compute f(x) given access only to Ax. An important example here are binary sketches (corresponding to p = 2). I will describe recent structural results about the smallest dimension of k which enables linear sketching using the tools of Fourier analysis and communication complexity. In particular, if f is an XORfunction linear sketching over Z_2 turns out to be the optimal tool for the design of twoplayer oneway communication protocols (under the uniform distribution of x) as well as multiplayer oneway broadcasting protocols with Omega(n) players (for any distribution of x).
Based on joint works with Kannan, Mossel and Sanyal (CCC'18), Hosseini and Lovett (CCC'19) and Zhou (RANDOM'19)"
October 22, 2019
Guannan Qu
Distributed optimization in multiagent systems: bridging the gap between centralized and distributed algorithms
We consider the distributed optimization problem over a network of agents, where the objective is to optimize a global function formed by a sum of local functions, with each agent only allowed to use local information and local communication with neighbors. This is a problem of fundamental interest in multiagent systems and has found various applications in sensor networks, multirobot systems, distributed machine learning, etc. To solve this problem, various distributed gradient methods have been proposed, but in this talk, we show there is a gap in convergence rate between the existing distributed gradient algorithms and the optimal centralized gradient algorithm. We then develop a gradient tracking technique that results in two algorithms that can partially bridge the gap. In particular, one of our algorithms achieves Nesterovtype acceleration in the realm of distributed optimization for the first time. Based on joint work with Na Li.
October 29, 2019
Guannan Qu
Exponential stability of primaldual gradient dynamics and its applications in network control
Primaldual gradient dynamics (PDGD) that find a saddle point of a Lagrangian of an optimization problem have been widely used in systems and control. In these applications, it is important for such dynamics to have strong stability guarantees, like global exponential stability. However, while the global asymptotic stability of PDGD has been wellstudied, it is less studied whether PDGD is globally exponentially stable.
In this talk, we study the primaldual gradient dynamics for constrained convex optimization and provide conditions that guarantee its global exponential stability. We also present its applications in a smart grid control problem.
November 5, 2019
☆ NOTE DIFFERENT TIME: 3:004:00PM ☆
Dean Doron
Nearly Optimal Pseudorandomness From Hardness
Existing proofs that deduce P=BPP from circuit lower bounds convert randomized algorithms to deterministic ones with a large polynomial slowdown in running time. In this talk, I will show that if we assume exponential lower bounds against nondeterministic circuits, we can convert any randomized algorithm running in time T to a deterministic one running in time T^{2+α} for an arbitrarily small constant α. Under complexitytheoretic assumptions, such a slowdown is nearly optimal.
Our result follows from a new pseudorandom generator whose construction uses, among other ideas, a new connection between pseudoentropy generators and locally listrecoverable codes.
Joint work with Dana Moshkovitz, Justin Oh and David Zuckerman
November 12, 2019
Eliza O'Reilly
Poisson hyperplane tessellations in high dimensions and onebit compression
In this talk, we will discuss random tessellations of R^n induced by stationary Poisson hyperplanes as the dimension n tends to infinity. We consider metrics of the cells of the tessellation motivated by the data compression method used in onebit compressed sensing. That is, assuming data in R^n is compressed using one bit with respect to each hyperplane, it is determined how the intensity of the hyperplanes must scale with n to ensure either sufficient separation of different data or sufficient proximity of data compressed together. This study leads to new insights on the nature of the cells of these tessellations in high dimensions and a connection with random polytopes defined as the convex hull of independent and identically distributed random points. Based on joint work with François Baccelli.
November 19, 2019
Eliza O'Reilly


201920 CMI Faculty Lunches
by invitation
April 11, 2019
Joel Tropp
SketchySVD
This talk asserts that randomized linear algebra is a natural tool for onthefly compression of data matrices that arise from largescale scientific simulations and data collection.
The technical contribution consists in a new algorithm for constructing an accurate lowrank approximation of a huge matrix from streaming data. Among other applications, we show how the SVD of a largescale sea surface temperature dataset exposes features of the global climate.
November 14, 2019
John Doyle
topic tba
April 09, 2020
Richard Murray
topic tba
