Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with skew circuits:
TR08-048 | 8th April 2008
Meena Mahajan, B. V. Raghavendra Rao

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 ... more >>>

TR14-183 | 25th December 2014
Nikhil Balaji, Andreas Krebs, Nutan Limaye

Skew Circuits of Small Width

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

TR15-022 | 9th February 2015
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for non-commutative skew circuits

Revisions: 1

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>

ISSN 1433-8092 | Imprint