Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATRIX RANK:
Reports tagged with Matrix Rank:
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 >>>

TR97-043 | 25th September 1997
Bruno Codenotti, Pavel Pudlak, Giovanni Resta

#### Some structural properties of low rank matrices related to computational complexity

Revisions: 1 , Comments: 1

We consider the conjecture stating that a matrix with rank
$o(n)$ and ones on the main diagonal must contain nonzero
entries on a $2\times 2$ submatrix with one entry on the main
diagonal. We show that a slightly stronger conjecture implies
that ... more >>>

TR03-079 | 8th November 2003
Scott Aaronson

#### Multilinear Formulas and Skepticism of Quantum Computing

Several researchers, including Leonid Levin, Gerard 't Hooft, and
Stephen Wolfram, have argued that quantum mechanics will break down
before the factoring of large numbers becomes possible. If this is
true, then there should be a natural "Sure/Shor separator" -- that is,
a set of quantum ... more >>>

ISSN 1433-8092 | Imprint