2023-2024 Seminars

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin  theorem (STOC 1989), which is the first local list-decoding algorithm.  We consider the following algorithmic problem: given oracle access to a function $f: Z_q^m...

I will give an introduction to the problem of sampling from a strongly log-concave density on Euclidean space through the lens of convex optimization.  In particular, I will focus on the interpretation, due to Jordan, Kinderlehrer, and Otto, of the...

In 1948, Shannon used a probabilistic argument to show the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major...

Recent years have seen remarkable progress in the field of Machine Learning (ML). 

However recent breakthroughs exhibit phenomena that remain unexplained and at times contradict conventional wisdom.  A primary reason for this discrepancy is that...

We will discuss a generalization of the celebrated Minimax Theorem (von Neumann, 1928) for binary zero-sum games. A simple game which fails to satisfy Minimax is Ephraim Kishon's “Jewish Poker” (see [1,2] below). In this game, each player picks a...

Random restrictions are a powerful tool used to study the complexity of boolean functions. Various classes of boolean circuits are known to simplify under random restrictions. A prime example of this, discovered by Subbotovskaya more than 60 years...

In this talk, I will present the following two connections between private optimization and statistical physics, both via the problem of approximating a given covariance matrix with a low-rank matrix:

1. An efficient algorithm to privately compute a...

Linear dynamical systems are the canonical model for time series data. They have wide-ranging applications and there is a vast literature on learning their parameters from input-output sequences. Moreover they have received renewed interest because...

It is widely believed that the physics of diffraction imposes certain fundamental limits on the resolution of an optical system. In this work we study the diffraction limit as a statistical inverse problem in increasingly more realistic mathematical...

This talk will summarize a project I was involved in during the past 8 years. It started with attempts to understand the PIT (Polynomial Identity Testing) problem - a central problem involving randomness and hardness. It has led us to pursue many...