Information-theoretic approximations of the nonnegative rank

DOI10.1007/S00037-016-0125-ZMaRDI QIDQ2012181zbMATH OpenOpenAlexFDO

Authors Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Publication date 28 July 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-016-0125-z

zbMATH Keywords

information theorynonnegative rankcommon information

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Common information and unique disjointness
• Nonnegative rank vs. binary rank
• Approximate nonnegative rank is equivalent to the smooth rectangle bound
• Approximate nonnegative rank is equivalent to the smooth rectangle bound
• Lower bounds on nonnegative rank via nonnegative nuclear norms

Cites work

• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• A short proof that the extension complexity of the correlation polytope grows exponentially
• An almost optimal algorithm for computing nonnegative rank
• An information statistics approach to data stream and communication complexity
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Common information and unique disjointness
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Elements of Information Theory
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Fractional Covers and Communication Complexity
• How to compress interactive communication
• Inapproximability of combinatorial problems via small LPs and SDPs
• Information Equals Amortized Communication
• Information Equals Amortized Communication
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Nondeterministic Quantum Query and Communication Complexities
• On the complexity of nonnegative matrix factorization
• On the distributional complexity of disjointness
• On the ratio of optimal integral and fractional covers
• The common information of two dependent random variables
• Values and Bounds for the Common Information of Two Discrete Random Variables

Cited in

(9)

• Extension complexity of formal languages
• Research trends in combinatorial optimization
• Common Information, Noise Stability, and Their Extensions
• Query complexity of sampling and small geometric partitions
• Exponential lower bounds for polytopes in combinatorial optimization
• Affine reductions for LPs and SDPs
• Extension complexity, MSO logic, and treewidth
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Common information and unique disjointness

This page was built for publication: Information-theoretic approximations of the nonnegative rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012181)