Computing Sparse Fourier Sum of Squares on Finite Abelian Groups in Quasi-Linear Time1
Computing Sparse Fourier Sum of Squares on Finite Abelian Groups in Quasi-Linear Time1
In this paper, we show that by performing the fast (inverse) Fourier transform, we can compute a sparse Fourier sum of squares (FSOS) certificate of f on a finite abelian group G with complexity that is quasi-linear in the order of G and polynomial in the FSOS sparsity of f. …