Information-theoretic approximations of the nonnegative rank
type: Item
instance of: scholarly article
title: Information-theoretic approximations of the nonnegative rank
zbMATH Open document ID: 1381.94044
author: Gábor Braun
author: Rahul Jain
author: Troy Lee
author: Sebastian Pokutta
published in: Computational Complexity
publication date: 2017-07-28T00:00:00Z
Mathematics Subject Classification ID: 94A17
Mathematics Subject Classification ID: 68P30
zbMATH DE Number: 6754727
zbMATH Keywords: nonnegative rank
zbMATH Keywords: common information
zbMATH Keywords: information theory
MaRDI profile type: Publication
full work available at URL: s00037-016-0125-z
OpenAlex ID: W2408372209
cites work: An information statistics approach to data stream and communication complexity
cites work: How to compress interactive communication
cites work: Common information and unique disjointness
cites work: Approximation Limits of Linear Programs (Beyond Hierarchies)
cites work: Inapproximability of Combinatorial Problems via Small LPs and SDPs
cites work: Information Equals Amortized Communication
cites work: Fractional Covers and Communication Complexity
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: Elements of Information Theory
cites work: Lower bounds on nonnegative rank via nonnegative nuclear norms
cites work: Exponential lower bounds for polytopes in combinatorial optimization
cites work: Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
cites work: A short proof that the extension complexity of the correlation polytope grows exponentially
cites work: On the ratio of optimal integral and fractional covers
cites work: Q5203681
cites work: An Almost Optimal Algorithm for Computing Nonnegative Rank
cites work: On the distributional complexity of disjointness
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: On the Complexity of Nonnegative Matrix Factorization
cites work: Values and Bounds for the Common Information of Two Discrete Random Variables
cites work: Nondeterministic Quantum Query and Communication Complexities
cites work: The common information of two dependent random variables
cites work: Expressing combinatorial optimization problems by linear programs
DOI: 10.1007/S00037-016-0125-Z
description: scientific article; zbMATH DE number 6754727