Title: Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time

Speaker:楊劍霆（ 博士研究生）中國科學院數學與系統科學研究院

Time: 3月3日（周四）10:00 AM

Venue:中科院軟件園區5號樓三層 337 會議室

Abstract: The problem of verifying the nonnegativity of a real valued function on a finite set is a long-standing challenging problem, which has received extensive attention from both mathematicians and computer scientists. Given a finite set $X$ together with a function $F:X \to \mathbb{R}$, if we equip $X$ a group structure $G$ via a bijection $\varphi:G \to X$, then effectively verifying the nonnegativity of $F$ on $X$ is equivalent to computing a  sparse Fourier sum of squares (FSOS) certificate of $f=F\circ \varphi$ on $G$. In this talk, we show that by performing the fast (inverse) Fourier transform, we are able to compute a sparse FSOS certificate of $f$ on $G$ with complexity $\operatorname{O}(|G|\log |G| + |G| t^4 + \operatorname{poly}(t))$, which is quasi-linear in the order of $G$ and polynomial in the FSOS sparsity $t$ of $f$. We demonstrate the efficiency of the proposed algorithm by numerical experiments on various abelian groups of order up to $10^6$.

Bio: 楊劍霆，中國科學院數學與系統科學研究院四年級博士研究生，導師為支麗紅研究員。