Recent results by Toda, Vinay, Damm, and Valiant have shown that the complexity of the
determinant is characterized by the complexity ofeounting the number ofaccepting …

We characterize the complexity of some natural and important problems in linear algebra. In
particular, we identify natural complexity classes for which the problems of (a) determining if …

We consider some algebraic models used in circuit complexity theory and in the study of the
complexity of the propositional calculus. This direction of research have been getting …

Closure under length-preserving homomorphisms is interesting because of its similarity to
nondeterminism. We give a characterization of NP in terms of length-preserving …

The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf
stringformed by concatenating the outcomes of all the computations in the tree in …

This paper provides logspace and small circuit depth analogs of the result of Valiant and
Vazirani, which is a randomized (or nonuniform) reduction from NP to its arithmetic analog⊕ …

On path equivalence of nondeterministic Inform?tion ~~;~zeing finite automata * Page 1
Information Processing Letters 58 ( 1996) 43-46 On path equivalence of nondeterministic …

FAST PARALLEL, COMPUTATION OF THE Page 1 Parallel Processing Letters Vol. 6 No. 2 (1996)
203-212 (c) World Scientific Publishing Company FAST PARALLEL, COMPUTATION OF THE …

The oracle separations proven by Baker, Gill, and Solovay [BGS75] initiated the study of
complexity classes by relativization. In order to study the NL=? L question, various …

The main result of this paper is a/spl Omega/(n/sup 1/4/) lower bound on the size of a
sigmoidal circuit computing a specific AC/sub 2//sup 0/function. This is the first lower bound …