Guy Moshkovitz, The City College and Graduate Center / CUNY

Abstract

Suppose that a polynomial has a biased output distribution; does this information alone suffice to deduce that its arithmetic complexity is far from maximal? This question turns out to be closely related to a central conjecture in additive combinatorics called the Gowers Inverse conjecture for polynomial phases, or the partition-vs-analytic rank conjecture. In this talk we will discuss recent progress on this problem, culminating in a proof of the conjecture up to logarithmic factors. The proof is "elementary", and relies on two new tools: polynomial identities for higher-order tensors, and a certain random walk on zero sets of polynomials.

Based on joint work with Daniel Zhu.

See: https://theory.cs.rutgers.edu/theory_seminar