Computer Science and Discrete Mathematics (CSDM)

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

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

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

Chernoff's bound states that for any A⊂[N] the probability a random k-tuple s∈([N]k) correctly `samples' A (i.e. that the density of A in s is close to its mean) decays exponentially in the dimension k. In 1987, Ajtai, Komlos, and Szemeredi proved...

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

A graph G is said to be Ramsey for a tuple of graphs (H1,...,Hr) if every r-coloring of the edges of G contains a monochromatic copy of Hi in color i, for some i. A fundamental question at the intersection of Ramsey theory and the theory of random...

The central problem of physics and quantum chemistry is to find the ground state energy of some physical system governed by quantum mechanics.  In mathematical terms, this means finding the lowest eigenvalue of some linear operator on a vector space...

In this talk, we will present a new approach for approximating large independent sets when the input graph is a one-sided expander—that is, the uniform random walk matrix of the graph has second eigenvalue bounded away from 1. Specifically, we show...

A cornerstone result in geometry is the Szemerédi–Trotter theorem, which gives a sharp bound on the maximum number of incidences between m points and n lines in the real plane. A natural generalization of this is to consider point-hyperplane...