Information-theoretic approximations of the nonnegative rank
DOI10.1007/S00037-016-0125-ZzbMATH Open1381.94044OpenAlexW2408372209MaRDI QIDQ2012181FDOQ2012181
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
Recommendations
Measures of information, entropy (94A17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Elements of Information Theory
- On the complexity of nonnegative matrix factorization
- Expressing combinatorial optimization problems by linear programs
- On the ratio of optimal integral and fractional covers
- A short proof that the extension complexity of the correlation polytope grows exponentially
- An information statistics approach to data stream and communication complexity
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Common information and unique disjointness
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- The common information of two dependent random variables
- Fractional Covers and Communication Complexity
- Title not available (Why is that?)
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- On the distributional complexity of disjointness
- Exponential lower bounds for polytopes in combinatorial optimization
- How to compress interactive communication
- Inapproximability of combinatorial problems via small LPs and SDPs
- Information Equals Amortized Communication
- Values and Bounds for the Common Information of Two Discrete Random Variables
- Nondeterministic Quantum Query and Communication Complexities
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Information Equals Amortized Communication
- An almost optimal algorithm for computing nonnegative rank
Cited In (9)
- Query complexity of sampling and small geometric partitions
- Exponential lower bounds for polytopes in combinatorial optimization
- Common information and unique disjointness
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Research trends in combinatorial optimization
- Extension complexity of formal languages
- Common Information, Noise Stability, and Their Extensions
- Extension complexity, MSO logic, and treewidth
- Affine reductions for LPs and SDPs
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)
