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