Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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