Video Lectures

In this talk I will describe a topological approach to some problems about algebraic functions due to Klein and Hilbert. As a sample application of these methods, I will explain the solution to the following problem of Felix Klein: Let $\Phi_{g,n}$...

Given a polynomial in one variable, what is the simplest formula for the roots in terms of the coefficients? Hilbert conjectured that for polynomials of degree 6,7 and 8, any formula must involve functions of at least 2, 3 and 4 variables...

The classical regression problem seeks to estimate a function f on the basis of independent pairs $(x_i,y_i)$ where $\mathbb E[y_i]=f(x_i)$, $i=1,\dotsc,n$. In this talk, we consider statistical and computational aspects of the "uncoupled" version...

Szemeredi's regularity lemma is an important tool in modern graph theory. It and its variants have numerous applications in graph theory, which in turn has applications in fields such as theoretical computer science and number theory. The first part...

Human memory is a multi-staged phenomenon of extreme complexity, which results in highly unpredictable behavior in real-life situations. Psychologists developed classical paradigms for studying memory in the lab, which produce easily quantifiable...

Given a family of m matchings in a graph G (where each matching can be thought of as a color class), a rainbow matching is a choice of edges of distinct colors that forms a matching. How many matchings of size n are needed to guarantee the existence...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

I will describe the problem of finding the homotopy type of the space of quantum Hamiltonians in dimension d under certain constraints. The common assumptions are that the interactions have finite range and that the ground state is separated from...

The "nearest neighbor (NN) classifier" labels a new data instance by taking a majority vote over the k most similar instances seen in the past. With an appropriate setting of k, it is capable of modeling arbitrary decision rules. Traditional...

In this talk, I'll illustrate how to lift a "small" locally testable code via a high dimensional expander (HDX) to a "large" locally testable code. Given a D-left regular bipartite graph G = ([n], [m], E) and a "small" code C \in {0,1}^D, the Tanner...