Computer Science & Discrete Mathematics (CSDM)

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.

We prove nearly quadratic (in the dimension) lower bounds for randomized algorithms for two basic problems: linear optimization and uniform sampling over convex bodies in the membership oracle model (a convex body K is specified by a point in K, the radii of two balls that sandwich K, and an oracle that takes any query point x and determines whether x is in K). For linear optimization, the lower bound matches the known nearly quadratic upper bound (up to a polylog factor in the dimension) and has further interesting consequences. Our construction, which is a distribution over parallelopipeds, also yields the same lower bound for randomized volume estimation.