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

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

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

Scott Aaronson

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