E Allender, R Beals, M Ogihara - … of the twenty-eighth annual ACM …, 1996 - dl.acm.org
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 …
P Pudlák, J Sgall - Proof complexity and feasible arithmetics, 1996 - users.math.cas.cz
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 …
JC Birget - Mathematical Systems Theory, 1996 - Springer
Closure under length-preserving homomorphisms is interesting because of its similarity to nondeterminism. We give a characterization of NP in terms of length-preserving …
B Jenner, P McKenzie, D Thérien - Information and Computation, 1996 - Elsevier
The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf stringformed by concatenating the outcomes of all the computations in the tree in …
A Gál, A Wigderson - Random Structures & Algorithms, 1996 - Wiley Online Library
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⊕ …
T Wen-Guey - Information Processing Letters, 1996 - Elsevier
On path equivalence of nondeterministic Inform?tion ~~;~zeing finite automata * Page 1 Information Processing Letters 58 ( 1996) 43-46 On path equivalence of nondeterministic …
JL Roch, G Villard - Parallel processing letters, 1996 - World Scientific
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 …
M Ogihara - Proceedings of the twenty-eighth annual ACM …, 1996 - dl.acm.org
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 …
P Koiran - … of Computational Complexity (Formerly Structure in …, 1996 - ieeexplore.ieee.org
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 …