Stale Polynomial and the Van der Waerden Conjecture
Shayan Oveis Gharan
10 July 2016, Isfahan University of Technology
I will talk about a relatively recent proof of the Van der Waerden Conjecture by Gurvits, and some applications in algorithm design.The main components of the proof is a novel application of stable polynomials. These family of polynomials have been recently employed to resolve several long standing open problems including approximability of traveling saleman problems, the Kadison-Singer conjecture and the existence of Ramanujan graphs.