Seminars

Natural gradient descent holds the potential to speed up training of neural networks by correcting for the problem geometry and achieving desirable invariance properties. I’ll present Kronecker-Factored Approximate Curvature (K-FAC), a scalable...

The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other...

The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems.

We will discuss PCPs...

Let X be the infinite graph partially pictured below, the "free product graph" C_4 * C_4 * C_4. Let FinQuo(X) be the set of all finite graphs G that covered by X (i.e., that 'locally resemble' X; i.e., that consist of C_4's joined 3-to-a-vertex). A...

For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph. A natural candidate to serve as universal graph G is the random graph G(n,p). In this case, we want to find an optimal p for...

A graph G is called a small set expander if any small set of vertices contains only a small fraction of the edges adjacent to it. This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was...

We consider adversarial online learning in a non-convex setting under the assumption that the learner has an access to an offline optimization oracle. In the most general unstructured setting of prediction with expert advice, Hazan and Koren (2016)...

Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a...

These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

M...