Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

Sharply Bounded Alternation within P

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 >>>

ISSN 1433-8092 | Imprint