Information-theoretic approximations of the nonnegative rank
From MaRDI portal
Publication:2012181
DOI10.1007/S00037-016-0125-ZzbMATH Open1381.94044OpenAlexW2408372209MaRDI QIDQ2012181FDOQ2012181
Troy Lee, Gábor Braun, Rahul Jain, 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
Measures of information, entropy (94A17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Title not available (Why is that?)
- 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
- The Matching Polytope has Exponential Extension Complexity
- 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
- 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)
- Exponential lower bounds for polytopes in combinatorial optimization
- Common information and unique disjointness
- Title not available (Why is that?)
- 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
- Query Complexity of Sampling and Small Geometric Partitions
- 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)
