Sparse Fourier sum-of-squares decomposition for nonnegative functions on abelian groups

Series
Algebra Student Seminar
Time
Friday, September 9, 2022 - 10:00am for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Shengding Sun – Georgia Institute of Technology – ssun313@gatech.edu – https://sites.google.com/view/ssdcgaddq
Organizer
Kevin Shu

(Based on paper by Fawzi, Saunderson and Parrilo in 2015) The space of complex-valued functions on a fixed abelian group has an orthonormal basis of group homomorphisms, via the well-known Discrete Fourier Transform. Given any nonnegative function with sparse Fourier support, it turns out that it’s possible to write it as a sum of squares, where the common Fourier support for all squares is not big. This can be used to prove results for the usual degree-based sum-of-squares hierarchy.