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

__
TR07-087
| 11th July 2007
__

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao#### Arithmetizing classes around NC^1 and L

Meena Mahajan, B. V. Raghavendra Rao

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

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

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