[2022-03-03]Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time

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: 杨剑霆，中国科学院数学与系统科学研究院四年级博士研究生，导师为支丽红研究员。