Events and Activities

In this talk, I'll show that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. This settles a long-standing open question in the area of low-degree testing, yielding...

It was conjectured by Alon in the 1980s that random d-regular graphs have the largest possible spectral gap (up to negligible error) among all d-regular graphs. This conjecture was proved by Friedman in 2004 in major tour de force. In recent years...

We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple new algorithm with a running time of O(m + n + log T)...

A common theme in mathematics is that limits of finite objects are well behaved. This allows one to prove many theorems about finitely approximable objects, while leaving the general case open --- examples for this are Gottschalk's conjecture...

In the previous talk, we defined Subgroup Tests and the interactive proof system induced by them. In addition, we showed that if the Aldous--Lyons conjecture was true, then this interactive proof system contains only decidable languages. In this...