We refine the techniques of Beigel et al.[4] who investigated polynomial-time counting
classes, in order to make them applicable to the case of logarithmic space. We define the …

ALGORITHMS INVENTED IN THE PAST 25 YEARS make it possible on a computer to
efficiently factor a polynomial in one, several, or many variables with coefficients from a …

The complexity of graph connectivity Page 1 The Complexity of Graph Connectivity Avi
Wigderson Hebrew University and Princeton University May 15, 1992 Abstract In this paper we …

In this paper, some classes of arithmetic circuits are introduced that capture the
computational complexity of computing the determinant of matrices with entries either …

A new approach to Buss's NC^1 algorithm Proc. 19th ACM Symposium on Theory of
Computing, Association for Computing Machinery, New York, 1987, pp. 123–131 for …

We present a machine learning system, called BONSAI, for knowledge acquisition from
positive and negative examples of strings, and report some experiments on protein data …

We develop a method for nontrivially restricting fanout in a circuit. We study the complexity of
the circuit value problem and a new problem, network stability, when fanout is limited. This …

This paper considers restrictions on Boolean circuits and uses them to obtain new uniform
circuit characterizations of nondeterministic space and time classes. It also obtains …

We generalize relational data bases such as to include also hierarchic structures in the form
of directories of relations and directories of directories. In this framework we study …

Given m finite automata, the emptiness of intersection problem is to determine whether there
exists a string which is accepted by all m automata. In the following we consider the case …