All reports by Author Jonathan F. Buss:

__
TR97-009
| 12th March 1997
__

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit#### The Computational Complexity of Some Problems of Linear Algebra

__
TR96-011
| 29th January 1996
__

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith#### Sharply Bounded Alternation within P

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

We consider the computational complexity of some problems

dealing with matrix rank. Let E,S be subsets of a

commutative ring R. Let x_1, x_2, ..., x_t be variables.

Given a matrix M = M(x_1, x_2, ..., x_t) with entries

chosen from E union {x_1, x_2, ..., ...
more >>>

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

We define the sharply bounded hierarchy, SBHQL, a hierarchy of

classes within P, using quasilinear-time computation and

quantification over values of length log n. It generalizes the

limited nondeterminism hierarchy introduced by Buss and Goldsmith,

while retaining the invariance properties. The new hierarchy has

several alternative characterizations.

We define ... more >>>