Systems | Information | Learning | Optimization

## A big conjecture in combinatorics that unexpectedly got proved last week and what this has to do with matrix multiplication

There’s a popular folk question about the card game Set: how many cards can you have on the table before there’s necessarily a legal play? The answer, which is pretty tricky to work out, and which is larger than most people expect, is 20. This is one case of a …

## Convex relaxations and the planted clique problem

Suppose G is a graph on N vertices, and H is a set of vertices on which someone has secretly “planted” a complete graph, or a graph whose edge-density is significantly greater than that of G. Can we efficiently and reliably find H, given G? This is called the “planted …

## Have you heard the good news about L^p graphons?

We talk a lot in this seminar about random graphs, and by this we often mean random graphs in the Erdos – Renyi sense. In recent years, the theory of graph limits or graphons has been developed; this gives us a very nice analytic way of describing various Erdos-Renyi-like graphs. …

## Similarity comparisons and non-metric clustering

Suppose given a set S of objects, together with some measure of dissimilarity between pairs of objects in S. It is an old and much-studied problem to find good embeddings of S into standard metric spaces (like the real plane, or a binary tree) so that the dissimilarities between objects …