Eric Allender, Robert Beals, Mitsunori Ogihara

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 a

system of linear equations is feasible and (b) computing the rank of

an integer matrix, ...
more >>>

Amihood Amir, Richard Beigel, William Gasarch

Let A(x) be the characteristic function of A. Consider the function

F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be

computed with fewer than k queries to some set X, then A can be

computed by polynomial size circuits. A generalization of this result

has applications to bounded query ...
more >>>

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Normally, communication Complexity deals with how many bits

Alice and Bob need to exchange to compute f(x,y)

(Alice has x, Bob has y). We look at what happens if

Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n

and they want to compute f(x_1,y_1)... f(x_n,y_n).

THis seems hard. We look at various ...
more >>>