Bias vs low rank of polynomials with applications to list decoding and effective algebraic geometry

Abhishek Bhowmick
University of Texas at Austin
December 7, 2015
Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields.

Ramanujan coverings of graphs

Doron Puder
Member, School of Mathematics
December 8, 2015
Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a $d$-covering which is also Ramanujan. This generalizes the $d = 2$ case, a recent major breakthrough in the subject due to Marcus, Spielman and Srivastava. The main tools we use are the Peter-Weyl theory in group representations, as well as the theory of interlacing polynomials. All notions will be explained. Joint work with Chris Hall and Will Sawin.