Authors: Neeraj Kayal, Vineet Nair, and Chandan Saha

Preseneter: Nimitt

RECAP.

. This Paper closes the Open Problem posed by Oliviera, 2013.

. Models:

ROABP.

$V_i → L(x_{\pi(i)}) → V_{i+1}$

Multilinear Depth 3 Circuits.

$\Sigma\Pi\Sigma$

Theorem 7.

. There is an explicit family of polynomials, $\{g_n\}_{n\ge 1}$ over any field $\mathbb{F}$ such that $g_n$ is computable by a MD3C over $\mathbb{F}$ of top fanin three but any ROABP over $\mathbb{F}$ computing $g_n$ has width $2^{\Omega(n)}$.

Theorem 9.

. Any multilinear depth three circuit computing $IMM_{n,d}$ has top fan in $n^{\Omega(d)}$.

PROOF (Theorem 7).

Expander Graphs.

Edge Expansion.

Let $G = (V, E)$ be undirected $d$-regular graph. The edge expansion of G is,

$h(G) = min_{S\subset V} \frac{|E(S,V-S)|}{|S|}$

Family of Expander Graphs.

Seqeunce of d regular graphs $\{G_n\}_{n\ge 1}$ is family of expander graphs if there exists an $\epsilon \gt 0$ such that $h(G_i) \gt \epsilon \ \forall i.$

Double Cover Expander Graphs.

For a d regular graph $G = (V,E)$ its double cover is graph $G’ = (L\uplus R, E')$ such that $|L| = |R| = |V|$ . For each vertex in V we have two vertices $u_L \in L$ and $u_R \in R$ and for each edge $(u,v) \in E$ we have two edges in $G’$ , $(u_L, v_R$) and$(v_L, v_R$). Note that G’ is also d regular. Infact, family of d regular expander graphs gives family of d regualar double graphs with $h(G'_i) \gt \frac{2+10^{-4}}{2}$

Perfect Matchings.

A $d$ regular bipartitie graph has $d$ edge disjoint perfect matchings.

Polynomial.

We use a family of 3 regular expander graphs, $F$ to construct the polynomial family. Let $G = (V,E)$ be a $n$-vertex graph in $F$, and$G’ = (L\uplus R, E’$) be its double cover. We construct a polynomial in variables $X = \{x_1, x_2,..x_n\}$ and $Y = \{y_1, y_2, …y_n\}, g(X,Y).$. Vertices in $L$ are assigned variables $X$ and vertices in R are assigned variables $Y$. Edges are $(1 + x_i + y_j)$. Let$M_1, M_2$ and $M_3$ be perfect matchings of $G’$. Then, g(X,Y) =$P_1 + P_2 + P_3$ where $P_i$is product of polyonomials corresponding to edges in $M_i$.

g is easy for MD3C.

MD3C of size $\Theta (n)$.

g is “hard” for ROABP.

Evaluation Dimension.

$EvalDim_S(f(X)) = dim(span\{f(X)|_{\forall x_j\in S, \ x_j=\alpha_j}: \forall x_j \in S \ \alpha_j \ \in \mathbb{F}\})$

ROABP EvalDim Bound.

Consider a width k ROABP R that computes g(X). Then, for every $i \in [0,|X|] \exists S$ such that$|S| = i$ $EvalDim_S(g)) \le k$.

EvalDim of g.

Evaluation Dimension of g with any subset $S$ of variables of size $n/10$ is large (exponential).

Classify linear terms in products as

. Completely Untouched

. Partially Untouched $[E'(S, V -S)]$

. Completely Touched

Let $B_i$ be set of partially touched linear polynomials in $P_i$. Using Expansion Property of $G$’,

$|E’(S, V-S)| \ge \frac{2+10^{-4}}{2}.\left( \frac{n}{10}\right)$

$T = max(|B_i|). \\ T \ge |E’(S,V-S)|/3.$

There exists a set $X_0 \subset X of (7n/10-4)$ $\ X$ variables such that every $x \in X_0$ appears in an untouched linear polynomial in every $P_i [ (1+x+y_{j_1}), (1+x+y_{j_2}),(1+x+y_{j_3})]$.

WLOG, assume $|B_1|\ge \epsilon n$ . Let $x$ and $x$’ be in$X_0$ such that they appear in untouched polynomials in $P_1, P_2$ and $P_3$. Get $g$’ by substituting $x = -(1+y_2$) and $x’ = -(1+y_3$).

Note that, $g’ = g|x,x’ = P_1’$.

$EvalDim(g) \ge EvalDim(g’) = EvalDim(P_1’)$

But, $P_1’$ is product of $\epsilon n$ linear polynomials, thus $EvalDim(P_1’) \ge 2^{\epsilon n}$

PROOF (Theorem 9).

Polynomial.

The polynomial is matrix multiplication of $d$ $(k + (k-1) + 4k)$ ($n\times n$) matrices:

. $k \ Y^i$ matrices: Each entry a variable. $|Y| = n^2k$

. $(k - 1) \ A^i$ matrices: all 1s

. $(r=4k) \ X^i$matrices: $X^1$ and $X^r$ are row and column matrices, rest diagonal. $|X| = 4kn$.

g = $….Y^i X^{(4i-1)} X^{(4i)} A^i X^{(4i+1)} X^{(4i+2)}….$

g is “hard” for MD3C.

Skewed Partial Derivates.

Let $f \in \mathbb{F}[X,Y]$, where $X$ and $Y$ are disjoint and $\mathcal{Y}_k$be set of all monomials in $Y$ variables of degree $k$. Then, partial derivative measure is

$PD_{\mathcal{Y}_k} = dim(span \{ [ \frac{\partial f(X,y)}{\partial m} ]_{\forall y \in Y \ y=0}: m \in \mathcal{Y}_k)\}$

Let $\mathcal{Y}_k$ be the set of monomials m formed by picking exactly one Y-variable from each of the matrices Y^i. Then $|\mathcal{Y}_k| =n^{2k}$.

$PD_{\mathcal{Y}_k}(g(X,Y) = |\mathcal{Y}_k| =n^{2k}$

For a multilinear depth 3 circuit, $PD_{\mathcal{Y}_k}(C) \;\le\; s(k+1)\binom{|X|}{k}.$ Thus,

$s \ge \frac{n^{2k}}{(k+1)\binom{4nk} {k}} \ge n^{\Omega(d)}.$