We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi2 o MOD o AC0 circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every ... more >>>

We extend the lower bound techniques of [Fortnow], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjascii's theorem from the Boolean setting to the arithmetic setting. This generalization is made possible, due to the recent discovery of logspace-uniform TC^0 circuits for iterated multiplication. ... more >>>

In this note, we consider the problem of computing the coefficients of the characteristic polynomial of a given matrix, and the related problem of verifying the coefficents. Santha and Tan [CC98] show that verifying the determinant (the constant term in the characteristic polynomial) is complete for the class C=L, and ... more >>>

The Pfaffian of an oriented graph is closely linked to Perfect Matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and determinant is usually exploited to give a fast algorithm for computing Pfaffians. We present the first completely combinatorial algorithm for ... more >>>

In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients of the characteristic polynomial, in terms of walks and closed walks of different kinds in the underlying graph. We develop algorithms based on ... more >>>

We prove a new combinatorial characterization of the determinant. The characterization yields a simple combinatorial algorithm for computing the determinant. Hitherto, all (known) algorithms for determinant have been based on linear algebra. Our combinatorial algorithm requires no division and works over arbitrary commutative rings. It also lends itself to efficient ... more >>>

We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of logarithmic depth are as powerful as uniform arithmetic circuits of polynomial degree; earlier proofs did not work in the uniform setting. This also provides a unified ... more >>>