Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

2021-06-14-LST-Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

paper

Results

• First superpolynomial lower bound against constant depth circuit for arbitrary depth.
• General Circuits
• Better bound against IMM for set multilinear circuits, namely $n^{d^{\exp(-\Delta)}}$ vs $f(d)\poly(n^2)$. (Theorem 2)
  • For large $d$ and small $\Delta$ this is stricly better.
• Convert any constant depth circuit to a constant depth set-multilinear circuit. (Lemma 10)
• Formal: Let $d=o(\log N)$ and $\mathbb{F}$ be characteristic zero or greater than $d.
• => There exists an explicit formal polynomial $P_{N,d}(x_1,\dots,x_N)$ that has no algebraic circuits of product depth $\Delta$
  • and size at most $N^{d^{\exp(-\Delta)}}$.
  • The polynomial is the IMM on $dn^2$ variables.
  • Notice that this bound scales with $\Delta$ and the polynomial is independent of $\Delta$.

Setup

• $w=(w_1,\dots,w_d)$ are weight vectors in $\mathbb{Z}\setminus {0}$.
• $w_S=\sum_{i\in S} w_i$, $P_w$ is all indices that have positive weight and $N_w$ all indices that have negative weight.
• $w$ is $b$-unbiased if $|w_I| \leq b$ for all interval $I\subseteq [d]$.
  • This implies $w_i\leq b$ (I think also $w_i\leq b/d$).
• Complexity measure:
  • For a given $w$ we take a matrix such that the rows are indexed by all possible monomials on the positive variables and the columns by all possible monomials on the negative variables.
  • The entry $(m_1,m_2)$ is the coefficient of $m_1m_2$ in $f$.
  • We define this as $M_w(f)$.
  • The measure is now the rank of $M_w(f)$ divided by the maximal possible rank,i.e, $rank(M_w(f))/\sqrt{ |M^P_w| |M^N_w| }$
  • This is equal to $rank(M_w(f))/2^{1/2 \sum_i |w_i| }$.
  • The usual properties hold.
• What is the main idea behind this measure?
  • I think this is just splitting the variables depending on the weight given, i.e., if it is positive or not.
  • This is in essence just partial derivatives to with respect to the negative set.
• Variables in set $X_i$ are labelled by ${0,1}^{ |w_i| }$.
  • Notice that the number of variables is also depending on the weight vector $w=(w_1,\dots,w_d)\in (\mathbb{Z}\setminus {0})^d$.
• The polynomial is now $P_w = \sum_{\sigma(m_+) \text{prefix} of \sigma(m_-) \text{or other way}} m$.
  • Here $\sigma(m_+)$ is the variable bit string of the positive monomial and $\sigma(m_-)$ of the negative monomial.
  • The variable bit string is just the bit string of the variables chosen as above.
  • This is still parameterized by $m$.
  • $w$ being $b$-unbiased will be the focus.
  • This is probably full rank because it looks like a triangle matrix.

Transforming the Circuit

• Let $s\geq Nd$ and $C$ be a homogeneous circuit of size at most $s$ and product depth $\Delta$.
• => Then there is a set multilinear circuit of size at most $(d!)s$ and product depth at most $\Delta$ computing the same polynomial with $|X_i|\leq N$.
• Proof Idea:
  • For every subset of variables create a new variable.
  • Split the gates into every possible subsets of size up to degree of the gate.
  • Addition gates and leaves are easy.
  • Product gates now have all possible decompositions.

Lower Bound

• Claim 14: Any product depth 2 circuit with $w\in {-k, \lfloor k-k/\sqrt{d}}$ has relrank$\leq s 2^{-k\sqrt{d}/s}$.
  • Notice that $w_i$ only has two possibilities.
  • Proof:
    • We can define $C=C_1 + \dots + C_t$ with $C_i$ of the form $\prod\sum\prod\sum$.
    • Define Type 1 if $C_i$ has degree $\geq \sqrt{d}/2$ and Type 2 otherwise.
    • Type 1 is easy.
    • For Type 2 it turns out that $|w^{ij}{S_j}| \geq k\deg(C{i,j})/2\sqrt{d}$ (the sum of its entries).
• Claim 16: Any set multilinear formula of product depth $\Delta$ for $w$ between $\alpha k$ and $-k$ has relrank at most $s2^{-kd^{1/(2^\Delta -1)}/20}$.
  • Proof similar to Claim 13 and via induction.