Hard pure math problems and hard algorithmic problems

In harmonic analysis and analytic number theory, many problems concern estimating the L^p-to-L^q norm of particular operators.  In CS, there is an interesting literature about the algorithmic problem of efficiently estimating the L^p-to-L^q norm of a given matrix.  We will discuss some connections between these areas.  

 

First, proof techniques in pure math are related to algorithms in CS.  We discuss a recent example.  Guth and Maynard recently made progress on the Montgomery large value problem in analytic number theory, related to the zeroes of the Riemann zeta function.  One part of the proof is a new argument for estimating L^p-to-L^q norms of matrices.  This new argument is closely related to a new algorithm that was independently discovered by Diakonikolas-Hopkins-Pensia-Tiegel.

 

Second, we explore ideas of hardness in both areas.  In pure math, hardness is mostly described subjectively.  In CS, there are many principled notions of hardness, such as NP-hardness and sum-of-squares-hardness.  We explore how much these CS ideas apply to pure math problems, using the examples above.  It is not always easy to relate these two types of hardness.  But we will see, for example, that the limits of our understanding for the Montgomery large value problem are related to the limits of sum-of-squares techniques in algorithmic problems about matrix norms.