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

Mrinal Kumar, Ben Lee Volk

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of ... more >>>