Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author B. V. Raghavendra Rao:

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

TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as
polynomial size formulae and bounded width branching
programs. Caussinus et al. \cite{CMTV} considered arithmetizations of
two of these classes, #NC^1 and #BWBP. We further this study to
include arithmetization of other classes. In particular, we show that
counting paths ... more >>>

ISSN 1433-8092 | Imprint