Algebraic Complexity Classes - Perspectives in Computational Complexity - page 57

We just introduced a new kind of circuit there: skew circuits. Are they as powerful
as general circuits? We do not know! Let's define VP skew ; p -families of polynomials
computed by polynomial-sized skew circuits. It turns out this is a great class to
study, because it exactly characterises the complexity of the determinant. Recall
what we have already seen;

VNC 1 and is in VP. The
upper bound proof from [ MV97 ] actually gives a skew circuit of size O

( Det n ) is hard for VF =

n 4 ,but

skew circuit constructions were known much earlier: in [ Ven92 ], Venkateswaran first
defined Boolean skew circuits to capture nondeterministic circuits, and subsequently
many authors independently extended that study to arithmetic rings, [ Dam91 , Tod92 ,
Vin91 , Va l 9 2 ]. And the lower bound proof from [ Va l 7 9 ] shows that polynomials
computed by skew circuits are p -projections of the determinant, though it is not
stated this way. Valiant showed that a formula can be converted to a certain kind of
graph that we nowadays call an algebraic branching program or ABP (more about
this below), and that polynomials computed by ABPs are p -projections of

( )

( Det n ) .

And we now know that ABPs are essentially skew circuits.
Time to define ABPs. These are directed acyclic graphs, with a designated source
node s and a designated target sink node t (sometimes there may be multiple target
nodes), and with edges labelled from

X (similar to input nodes in a circuit). For
any directed path ʻ , the weight of ʻ is the product of the labels of the edges on ʻ .
The polynomial p v computed at a node

F

v is the sum of the weights of all directed

s paths. The polynomial computed by the ABP is just p t . Families computed by

polynomial-size ABPs form the class VBP. (In some parts of the literature, edge
labels are allowed to be linear forms in X . This does not significantly change the
properties of ABPs as we discuss here. We'll stick to the convention that labels are
in

v

X .)
So why are ABPs and skew circuits essentially the same? ABPs to skew circuits:
clearly, p s

F

1, and for any other source node (in-degree 0) s , p s

= = 0. Look at

an edge u ∗ v of the ABP with label ʲ . Then p has a contribution from p u × ʲ .

v

Summing this over all incoming edges at from

previously computed values, and this circuit is skew. For the reverse simulation,
reverse this construction: (1) introduce a source node s , (2) for each input node u
labelled

v gives a small circuit computing p

v

u , create edges

ʲ , add an edge s ∗ u labelled ʲ , (3) for each node v = u +

u ∗ v and u ∗ v labelled 1, and (4) for each node v = u × ʲ , create an edge u ∗ v

labelled .

So now we can add to the list of results at the end of Sect. 4.2 :

ʲ

( Det n ) is complete

for VBP VP skew under p -projections.

In fact, we can add more. What makes the simulation from skew circuits to ABPs
possible is the fact that at each

=

gate, one argument is easy . Toda [ Tod92 ] took
this argument further—it is enough if one argument is independent of the rest of
the circuit. That is, for each

×

node ∂ = ʲ × ʳ , the entire sub-circuit rooted at
either ʲ or ʳ has no connection to the rest of the circuit except via this edge to ∂ .
(Equivalently, one of the edges into ∂ is a bridge in the circuit.) Call such circuits
weakly skew circuits. Toda showed that weakly skew circuits can be converted to
skew circuits with linear size blow-up. See also [ MP08 ], where Malod and Portier

×