"Tensor Tools for Problems in Combinatorics and Complexity"
Jeoren Zuiddam (NYU)
Monday, January 4th 2021, 2-3pm
Abstract:
Understanding notions of "independence" is a central problem in algebraic complexity theory (the complexity of matrix multiplication), extremal combinatorics (the cap set problem and the sunflower problem), quantum information theory (the resource theory of entanglement), property testing, and communication complexity.
We will talk about tensors as a tool to understand independence, both asymptotically and non-asymptotically, and in particular see how a recent geometric approach called Geometric Rank (Kopparty–Moshkovitz–Zuiddam, 2020) solves a problem of Strassen about matrix multiplication. Finally, we will explore different potential approaches to understanding independence.