Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with matrix factorization:
TR12-053 | 30th April 2012
Ankur Moitra

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

TR18-029 | 9th February 2018
Neeraj Kayal, vineet nair, Chandan Saha

Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

Revisions: 2

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>

ISSN 1433-8092 | Imprint