| February 10th | Jonathan Tidor (MIT Mathematics) |
Communication complexity | Two parties, Alice and Bob, each have some input $x$ and $y$. Their goal is to communicate to compute a function $f(x,y)$ of their inputs. For which functions $f$ (and which models of communication) is it possible for Alice and Bob to communicate few bits of information and still compute $f(x,y)$? Such problems are studied in communication complexity, a field of theoretical computer science. In this talk we will see several interesting communication protocols and also many lower bounds using ideas from graph theory, linear algebra, and probabilistic and additive combinatorics. |
| February 17th | Guanghao Ye (MIT Mathematics) |
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time | We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior-point methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\text{poly}(\log n))$ time [Daitch-Spielman, STOC'08]. Our results immediately extend to all families of separable graphs. This is joint work with Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, and Sushant Sachdeva. |
| February 24th | Nitya Mani (MIT Mathematics) |
Nim and variants | Nim is perhaps the most famous of impartial combinatorial games, with a simple solution initially given by Bouton. Many generalizations of Nim and other impartial combinatorial games have been closely studied since the work of Bouton. We will survey a collection of interesting Nim variants and some associated results, along the way encountering Fibonacci numbers, simple solutions, and surprisingly complicated dynamics. |
| March 3rd | Rachel Zhang (CSAIL) |
Interactive Error Correcting Codes | Consider the task of communicating a message x to a receiver in an error resilient way. Classically, error correcting codes provide a non-interactive solution to this problem: the sender can simply encode x using an error correcting code, so that even if a constant fraction of the bits are adversarially corrupted, the receiver can still correctly learn x. In this talk, I will define the notion of an interactive error correcting code and show that over a binary alphabet, they can tolerate more adversarial erasures than can (non-interactive) error correcting codes. This is joint work with Meghal Gupta and Yael Tauman Kalai. |
| March 10th | George Stepaniants (MIT Mathematics) |
Learning and predicting complex systems dynamics from single-variable observations | Advances in model inference and data-driven science have enabled the accurate discovery of governing equations from observations alone, accelerating our understanding and control of dynamical systems. However, despite the ever-growing amount of experimental data collected, many physical and biological systems can only be partially observed. Here, building on recent progress in the inference and integration of nonlinear differential equations, we introduce an approach to learn a model using observations of just a single variable within a multi-variable dynamical system, and use this model to accurately predict future dynamics. Furthermore, we validate our approach on a variety of physical, chemical and biological systems which exhibit nonlinear dynamics such as relaxation oscillations and limit cycles. This is joint work with Alasdair Hastewell, Dominic Skinner, Jan Totz and Jörn Dunkel. |
| March 24th | No Seminar / Spring Break | ||
| March 31st | Alex Cohen (MIT Mathematics) |
A discrete 2D fractal uncertainty principle | A fractal uncertainty principle (FUP) states that a function `f' and its Fourier transform cannot both be large on a fractal set. These were recently introduced by Semyon Dyatlov and collaborators in order to prove new results in quantum chaos. So far FUPs are only understood for fractal sets in R, and fractal sets in $R^2$ remain elusive. In this talk, we prove a sharp fractal uncertainty principle for Cantor sets in Z/NZ x Z/NZ, a discrete model for $R^2$. |
| April 7th | Andrey Khesin (MIT Mathematics) |
Bound Secrecy and Bound Entanglement: Where (Qu)Bits Go to Die | There is a surprising result in information theory where the quantum version of a conjecture is known to be true, and the classical one remains open. The conjecture is that there exists a joint probability distribution for three parties, Alice, Bob, and Eve, that exhibits bound secrecy. Simply put, bound secrecy is the idea that there can secret information present in the correlations of the random variables belonging to Alice and Bob but that is completely unknown to Eve, and yet despite this, no matter what Alice and Bob say to each other publicly, they will be unable to distill any bits of a secret key, random bits completely unknown to Eve. This is a very surprising fact, as it seems that there is a secret that Alice and Bob share and yet cannot access despite their best efforts. The quantum version of this conjecture states that there exist joint states for Alice and Bob which are entangled and therefore cannot be created without spending some amount of entanglement, but from which no pure entangled states, such as Bell pairs, can be distilled. These joint states are called bound entangled, and not only are they known to exist, some small examples have been found. |
| April 14th | Byron Chin (MIT Mathematics) |
Reconstruction on the stochastic block model | The problem of community detection is one of great relevance in machine learning and data science. The goal is to group vertices that behave similarly within a graph or network. In the context of this problem, the Stochastic Block Model is one of the most well-studied random graph models. In this talk, we discuss reconstruction results for this model, highlighting a provably optimal algorithm that is closely related to belief propagation. |
| April 21th | Brice Huang (MIT EECS) |
Tight Algorithmic Thresholds from the Branching Overlap Gap Property |
We will describe recent progress on algorithmic hardness results for ``spin glass-like" random optimization problems.
The landscapes of these problems are highly nonconvex and often include many bad local maxima, impeding optimization
by efficient algorithms. As a result, these problems exhibit gaps between the largest objectives that exist and that
can be found by efficient algorithms; characterizing the algorithmic limit requires developing sharp hardness results.
For mean field spin glasses, we describe a new hardness result that tightly characterizes the algorithmic limit for
any algorithm with $O(1)$-Lipschitz dependence on the disorder coefficients. This class includes the best algorithm known
for this problem and natural formulations of gradient descent and approximate message passing.
We will go over the Overlap Gap Property (OGP) framework of Gamarnik and Sudan, which shows hardness in random optimization problems against any algorithm that is suitably stable in its inputs. We introduce the \emph{Branching OGP}, a generalization of the OGP to arbitrary ultrametric constellations of solutions, which is the key tool in the proof of the aforementioned hardness result. By considering the Continuous Random Energy Model (CREM), we will see by analogy why the Branching OGP yields tight algorithmic thresholds in mean field spin glasses and potentially in greater generality. Based on joint works with Guy Bresler and Mark Sellke. |
| April 28th | Anders Aamand (MIT CSAIL) |
Online Sorting and its Connection to Geometric Packing Problems |
We investigate various online packing problems in which convex polygons arrive one by one and have to be placed irrevocably
into a container before the next piece is revealed; the pieces must not be rotated, but only translated. The aim is to minimize
the used space depending on the specific problem at hand, e.g., the strip length in strip packing, the number of bins in bin packing, etc.
We draw interesting connections to the following online sorting problem: We receive a stream of real numbers $s_1, \cdots ,s_n,$ each from the unit interval $[0,1],$ one by one. Each real must be placed in an array with n initially empty cells without knowing the subsequent arriving reals. The goal is to minimize the sum of differences of consecutive reals in A. The offline optimum is to place the reals in sorted order, so the cost is at most 1. We will see that no online algorithm can achieve a cost lower than $n^{(1/2)}$ in the worst case. We use such lower bound to answer several fundamental questions about packing. Specifically, we prove the non-existence of competitive algorithms for various online packing problems. A surprising corollary is that no online algorithm can pack translates of convex polygons into a unit square even if we are guaranteed that the total area of the pieces is at most 0.000001 and the diameter of each piece is at most 0.000001. |
| May 5th | Travis Dillon (MIT Mathematics) |
Fair partitioning? It's a piece of cake! | Is it always possible to cut a cake and distribute the pieces so that everyone at a party gets the piece they most desire? We'll show that when it comes to cutting cakes, the old adage that you can't please everybody is dead wrong: Everyone can have their cake and eat it, too. Also, we'll prove Brouwer's fixed point theorem without using any topology. |
Sponsored by A Priori Investments