Algebraic Complexity Classes - Perspectives in Computational Complexity - page 62

This question is trickier than it seems at first glance, because given a circuit,
even checking whether it is multilinear is non-trivial. Fournier, Malod and Mengel
[ FMM12 ] recently observed that checking multilinearity of a given circuit is com-
putationally equivalent to the well-studied problem arithmetic circuit identity testing
(ACIT)—checking if a given circuit computes the identically zero polynomial.
So we may want a notion of certifiably multilinear circuits. One such notion is
that of syntactic multilinearity, SM. A circuit is said to be syntactically multilinear
if at every

node ∂ = ʲ × ʳ , the sub-circuits rooted at nodes ʲ and ʳ operate on
disjoint sets of variables. Note that this is much more restrictive than multiplicative
disjointness. But it certifies multilinearity, since no variable can ever get multiplied
by itself. And syntactic multilinearity is easy to check computationally: it is violated
if there is some node ∂ = ʲ × ʳ , some variable x , two input nodes I

×

I labelled x , ,

and paths from I to ʲ and I to ʳ .
If a family has efficient (polynomial-sized) SM circuits, then it has efficient mul-
tilinear circuits. The converse may not be true. But it is true if we look at formulas.
Given a multilinear formula, identify an SM violation ∂, ʲ, ʳ, x as above. Then we

know by multilinearity of the polynomial p (∂) that x does not appear in either p (ʲ)

or p . In the appropriate subformula, set all instances of x to 0; the polynomials

computed at and above ∂ remain unchanged. Doing this systematically gives an SM
formula of size no more than the original multilinear formula.
In the first major breakthrough, Raz [ Raz09 ] showed that for computation by SM
formulas, and hence by multilinear formulas, both

(ʳ)

( Det n ) and ( Perm n ) need size

n ˇ( log n ) . Clearly, this also means that they are not in SM-VNC 1 .
Since

(

Det n )

is in VP and even in VBP, SM-VF is strictly weaker than VBP. But
this is hardly a fair comparison: we have restricted VF to be SM, but not VBP and
VP. Can we say that SM-VF is strictly weaker than SM-VBP or SM-VP? We do not
know whether is in multilinear VP, let alone SM-VP, so a different family

is needed as a separating example. Such an example was provided soon thereafter,
again by Raz [ Raz06 ]. He constructed an explicit polynomial family that is in SM-
VP and even in SM-VSAC 1 , and showed that it needs SM-formula size n ˇ( log n ) and
hence is not in SM-VNC 1 . Improved lower bounds for constant-depth circuits and
subclasses of formulas were subsequently obtained by Raz, Shpilka and Yehudayoff
(see for instance [ RY09 , RSY08 ]).
Let's step back a bit.Why didwe say “in SM-VP, and even in SM-VSAC 1 ”?Aren't
VP and VSAC 1 the same? Well, we know that VP and VF can be depth-reduced. But
canwe assume that these depth reduction tehniques preserve syntacticmultilinearity?
Fortunately, they do; Raz and Yehudayoff [ RY08 ] showed that the depth reduction
of [ VSBR83 ] preserves SM, so indeed SM-VP= SM-VSAC 1 . Similarly, in [ JMR12 ]
it is observed that the formula depth reduction of [ Bre74 ] also does preserves SM,
so SM-VF= SM-VNC 1 .
What about other relationhips between the algebraic classes? We had considered
ABPs—what certifies multilinearity there? It is easy to see that a read-once restric-
tion, where on each path in the ABP each variable appears as a label at most once,
does so. Let us therefore use read-once as the definition of syntactic multilinearity
in ABPs. Then, as observed in [ JMR12 ], the Savitch-style divide-and conquer argu-

( Det n )