2021-2022 Seminars

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). One of the main methods...

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas.  In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is...

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). On the existential side...

Understanding the behavior of multi-player (multi-prover) games under parallel repetition is an important problem in theoretical computer science.

In a $k$-player game $G$, a referee chooses questions $(x^{1}, ..., x^{k})$ from a (publicly known)...

Gaussian elimination is one of the oldest and most well-known algorithms for solving a linear system. In this talk, we give a basic, yet thorough overview of the algorithm, its variants, and standard error and conditioning estimates. In addition, a...

Since the late 19th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a ``nice” way.  Of particular importance in computer science is the...

Training a predictor to minimize a loss function fixed in advance is the dominant paradigm in machine learning. However, loss minimization by itself might not guarantee desiderata like fairness and accuracy that one could reasonably expect from a...

Blockchains that support a general contract layer (e.g., Ethereum) export the functionality of a general-purpose, ownerless, and open-access computer that can enforce property rights for digital data.  How is such functionality implemented?  Using a...

The study of nodal sets, i.e. zero sets of eigenfunctions, on geometric objects can be traced back to De Vinci, Galileo, Hook, and Chladni. Today it is a central subject of spectral geometry. Sturm (1836) showed that the n-th eigenfunction of the...

A nodal domain of a Laplacian eigenvector of a graph is a maximal connected component where it does not change sign.  Sparse random regular graphs have been proposed as discrete toy models of "quantum chaos", and it has accordingly been conjectured...