Back to notes

# Arithmetic Circuits

## My notes on Arithmetic Circuits

Topics Progress HTML PDF
Depth reduction
80%
$\Det_n$ is $\VBP$-complete
50%
Arithmetic Models
10%
Partial Derivative
0%
Useful tricks
20%
$\VP = \VNP$ and GRH implies $\Ppoly = \NPpoly$
80%
Lower bounds - Depth 3
20%
Multilinear circuits and formulas
20%

## Preliminaries

### Common polynomials

• Elementary symmetric polynomials: Given $d\leq n$, the $n$-variate degree-$d$ elementary symmetric polynomial is defined as $\Sym_d(x_1,x_2,\dots,x_n)=\sum_{S\subseteq[n]:\ \card{S}=d}\prod_{i\in S}x_i$.

• Power-sum symmetric polynomials: Given $d\leq n$, the $n$-variate degree-$d$ power-sum symmetric polynomial is defined as $\Pow_d(x_1,x_2,\dots,x_n)=\sum_{i\in[n]}x_i^d$.

### Common arithmetic circuit complexity classes

For short, arithmetic circuit is a computational model consists of sum and product gates (sometimes power gate or other gate would be considered).Each circuit is associated with a digraph where each vertex is the arithmetic gate and the edge indicate where are the inputs from and output goes. Usually there will be $n$ inputs (for determinant/permanant problems there will be $n^2$ inputs) and single output (homogeneous circuit will produce multiple outputs each correspond to one degree).

When we discuss arithmetic ciruict, we usually mean a family of circuits where each length of the input has the corresponding circuit. Thus, a family of circuit computes a family of polynomials. We say a family of polynomials $f=\{f_n\}$, e.g., the elementary symmetric polynomials, has circuit complexity $s(f)\leq s(n)$ if for each $n\in\N$, there exists a size $s(n)$ arithmetic circuit that computes $f_n$.

We say $f\in\VP$, which is the analog of $\P$ in arithmetic circuit complexity, if $s(f)=\poly(n)$ and the degree of that circuit family is polynomially bounded.

## Lower bounds (Known results)

### $\Sigma\Lambda\Sigma$

• $2^{\Omega(n)}$ for $\Sym_n$ via linear algebraic argument. See this video.
• $2^{\Omega(n)}$ for $\Det_n$ and $\Perm_n$ using parital derivative. See Chapter 7.1.2 of this survey.

### $h-\Sigma\Pi\Sigma$

• $n^{\Omega(d)}$ for $\Sym_d$.

### $\Sigma\Pi\Sigma$

• $\Omega(n^2)$ wires for $\Sym_d$ with $d=n/100$.
• Over field of size at least $n+1$, $\Sym_d$ can be computed with size $O(n^2)$.
• $\Omega(n^3/\log^2 n)$ multiplication gates for some explicit polynomials.
• If $\card{\mathbb{F}}=O(1)$, then $n^{\Omega(d)}$ for $\Sym_d$ and $2^{\Omega(n)}$ for $\Det_n$, and $\Perm_n$.

### $h-\Sigma\Pi\Sigma\Pi$

• $n^{\omega(\sqrt{d})}$ implies $\VP\neq\VNP$.
• $2^{\Omega(\sqrt{n})}$ with bottom fan-in at most $O(\sqrt{n})$ for $\Det_n$ and $\Perm_n$ via shifted parital derivative.
• $n^{\Omega(n)}$ with bottom fan-in at most $O(\sqrt{n})$ for $NW_{\epsilon\sqrt{n}}$ via shifted parital derivative.
• $n^{\Omega(d)}$ with bottom fan-in at most $O(\sqrt{n})$ for $IMM_{n,d}$ with $d\leq n^{\delta}$ via shifted partial derivative.
• $d^{\Omega(\sqrt{d})}$ for $NW_{d,d^3,d/3}\circ Lin$ via surrogate rank approach.
• $n^{\Omega(\sqrt{d})}$ for $IMM_{n,d}$ via leading polynomial approach.

## Open problems

### Big direction

• (Open) Show a super-polynomial separation between arithmetic formulas, arithmetic branching programs, and arithmetic circuits. That is, show the following containments are strict: $\VF\subseteq\VBP\subseteq\VP\subseteq\VNP$.
• Univariate polynomial
• (Open) Find an explicit family of polynomial ${f_n}$ where $f_n$ is of degree $n$ such that $S(f_n)\neq(\log n)^{O(1)}$.
• (Conjecture) $S((x+1)(x+2)\cdots(x+n))\neq(\log n)^{O(1)}$.
• If the conjecture is false, then factoring can be computed in poly-size boolean circuits.
• Multivariate polynomial
• (Open) Find an explicit family $\{f_n\}$ of polynomials such that $S(f_n)=n^{\omega(1)}$.
• (Open) Find an explicit family $\{f_n\}$ of constant-degree polynomials such that $S(f_n)=\omega(n)$.

### Elementary symmetric polynomials

First, let’s list what we’ve know about elementary symmetric polynomials. (To the best of my knowledge)

• $\binom{n}{d}$ $\Sigma\Pi$ lower bound.
• $\Theta(n^2)$ non-homogeneous $\Sigma\Pi\Sigma$ and thus $d^{O(\sqrt{d})}\cdot\text{poly}(n)$ homogeneous $\Sigma\Lambda\Sigma\Lambda\Sigma$.
• $\frac{\binom{n}{d/2}}{2^d}$ homogeneous $\Sigma\Pi^{[d]}\Sigma$ lower bound.
• $\Theta(2^n)$ homogeneous $\Sigma\Lambda\Sigma$ and homogeneous $\Sigma\Lambda\Sigma\Lambda$.
• $2^{O(\sqrt{d})}\cdot\text{poly}(n)$ non-homogeneous $\Sigma\Lambda\Sigma\Lambda$.
• (This note) $2^{\Theta(\sqrt{d})}$ homogeneous bottom two symmetric $\Sigma\Pi\Sigma\Lambda$.

The following is what we don’t know. (To the best of my knowledge)

• Non-homogeneous $\Sigma\Lambda\Sigma\Lambda$ lower bound.
• Homogeneous $\Sigma\Lambda\Sigma\Lambda\Sigma$ lower bound for elementary symmetric polynomials. Even quadratic or super-polynomial lower bounds would be interesting.