Computer Science/Discrete Mathematics Seminar I

Last year there were two sensational and independent breakthroughs on the Chowla cosine problem, each giving polynomial bounds for the first time. One by Bedert who used a very clever, but more “direct” Fourier argument. On the other hand, the other proof, due to Jin, Milojević, Tomon, Zhang, went through a spectral graph theory argument which also made a fascinating connection with the problem of finding the densest cut in graphs containing no large clique.

In this talk I will discuss some recent work of myself with Bedert where we use the ideas of Bedert’s Fourier proof in the setting of graphs. The result is an interesting and unusual spectral proof that is surprisingly short in addition to giving a sharp bound on the “graph” Chowla problem.