Quasi-Linear Relation Between Structure and Randomness

Start Date: April 26, 2023
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Guy Moshkovitz - The City College and Graduate Center / CUNY
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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.

Events