Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOWER BOUND ON EXTENSION COMPLEXITY:
Reports tagged with lower bound on extension complexity:
TR13-158 | 18th November 2013
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Information-theoretic approximations of the nonnegative rank

Revisions: 3

Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication ... more >>>




ISSN 1433-8092 | Imprint