Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Linear Circuits:
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 >>>

TR19-047 | 2nd April 2019
Mrinal Kumar, Ben Lee Volk

Lower Bounds for Matrix Factorization

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

ISSN 1433-8092 | Imprint