Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-048 | 8th April 2008 00:00

Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae



Functions in arithmetic NC1 are known to have equivalent constant
width polynomial degree circuits, but the converse containment is
unknown. In a partial answer to this question, we show that syntactic
multilinear circuits of constant width and polynomial degree can be
depth-reduced, though the resulting circuits need not be syntactic
multilinear. We then focus specifically on polynomial-size syntactic
multilinear circuits, and study relationships between classes of
functions obtained by imposing various resource (width, depth, degree)
restrictions on these circuits. Along the way, we obtain a
characterisation of NC1 (and its arithmetic counterparts) in terms
of log width restricted planar branching programs. We also study the
power of skew formulae, and show that even exponential sums of these
are unlikely to suffice to express the determinant function.

ISSN 1433-8092 | Imprint