2019-2020 Seminars

Continuing last week's lecture, among the numerous applications of the regularity lemma, a classical one is the graph removal lemma. It has applications in fields such as number theory and theoretical computer science. For every fixed graph H, the H...

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple...

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...

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...

This talk focuses on a general phenomenon of "Frequency-Principle" that DNNs often fit target functions from low to high frequencies during the training. I will present empirical evidences on real datasets and deep networks of different settings as...

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...

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...

Minimax optimization, especially in its general nonconvex formulation, has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs) and adversarial training. It brings a series of unique...

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...