ECCC-Report TR08-048https://eccc.weizmann.ac.il/report/2008/048Comments and Revisions published for TR08-048en-usTue, 29 Apr 2008 20:39:18 +0300
Paper TR08-048
| Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae |
Meena Mahajan,
B. V. Raghavendra Rao
https://eccc.weizmann.ac.il/report/2008/048
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.
Tue, 29 Apr 2008 20:39:18 +0300https://eccc.weizmann.ac.il/report/2008/048