Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with identity-testing:
TR09-058 | 4th July 2009
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

We present new deterministic algorithms for several cases of the maximum rank matrix completion
problem (for short matrix completion), i.e. the problem of assigning values to the variables in
a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to
the fundamental problems in computational complexity ... more >>>

ISSN 1433-8092 | Imprint