Border Complexity of Sum-Power-Sum Circuits
Speaker: Chi-NingTitle: Border Complexity of Sum-Power-Sum Circuits
Date: 07 Oct 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Food: Indian
Audience background: Linear algebra and tensor
Talk style: Interactive whiteboard talk
Abstract: Given a homogeneous polynomial $f\in\mathbb{F}[x_1,\dots,x_n]$, it is known that $f$ can be computed by a Sum-Power-Sum circuits, i.e., sum of power of linear forms. The complexity of a Sum-Power-Sum circuit is naturally defined as the number of summands in the top Sum gate. Sum-Power-Sum circuit is considered as the weakest non-trivial circuit class in the arithmetic setting and there exists strong exponential lower bound ($2^{n-1}$ for $x_1\cdots x_n$).
In this talk, I’m going to put the Sum-Power-Sum circuits into the context of Geometric Complexity Theory (GCT). That is, we are going to study the border complexity of Sum-Power-Sum circuits. Formally, we say a Sum-Power-Sum circuit $C$ $\epsilon$-approximates $f$ if $\abs{f(x)-C(x)}$ for all $x\in\mathbb{F}^n$. The border Sum-Power-Sum complexity of $f$ is then defined as the smallest number $s$ such that for all $\epsilon>0$, there exists a size $s$ Sum-Power-Sum circuit that $\epsilon$-approximates $f$. It is an interesting open problem in GCT to understand whether the Sum-Power-Sum complexity is polynomially related to its border complexity.
In this talk, I’ll start with some basic setup and examples of the Sum-Power-Sum circuits and border complexity. Then, I’ll let the audience to decide if they would like to hear more on the motivation of this problem (background of GCT) or more on the recent developments (using representation theory and Lie algebra to understand the border Sum-Power-Sum complexity of monomials).