Graph isomorphism is the prime example of a computational problem with a wide difference
between the best known lower and upper bounds on its complexity. There is a significant …

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 …

Parallel arithmetic computations: A survey Page 1 PARALLEL ARITHMETIC COMPUTATIONS:
A SURVEY Joachim yon zur Gathen University of Toronto Abstract A survey of parallel …

This conference (ANTS-I) marks the beginning of what we hope will be a long series of
international conferences on algorithmic number theory. It seems appropropriate, at the …

Smale's 17th problem asks:“Can a zero of $ n $ complex polynomial equations in $ n $
unknowns be found approximately, on the average, in polynomial time with a uniform …

A conjecture of Jozsa (arXiv: quant-ph/0508124) states that any polynomial-time quantum
computation can be simulated by polylogarithmic-depth quantum computation interleaved …

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 …

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially
equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic …

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 …