Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

For an $n$-variate order-$d$ tensor $A$, define $A_{\max }:={\sup }_{\Vert x{\Vert }_2=1}⟨A,x^{\otimes d}⟩$ to be the maximum value taken by the tensor on the unit sphere…