Information-theoretic approximations of the nonnegative rank
From MaRDI portal
Publication:2012181
DOI10.1007/s00037-016-0125-zzbMath1381.94044OpenAlexW2408372209MaRDI QIDQ2012181
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
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17)
Related Items (9)
Common information and unique disjointness ⋮ Research trends in combinatorial optimization ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ Unnamed Item ⋮ Affine reductions for LPs and SDPs ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Lower bounds on nonnegative rank via nonnegative nuclear norms ⋮ Extension complexity of formal languages ⋮ Common Information, Noise Stability, and Their Extensions
Cites Work
- Unnamed Item
- Common information and unique disjointness
- An information statistics approach to data stream and communication complexity
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- On the ratio of optimal integral and fractional covers
- A short proof that the extension complexity of the correlation polytope grows exponentially
- 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
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- On the Complexity of Nonnegative Matrix Factorization
- The common information of two dependent random variables
- Values and Bounds for the Common Information of Two Discrete Random Variables
- The Matching Polytope has Exponential Extension Complexity
- Nondeterministic Quantum Query and Communication Complexities
- Fractional Covers and Communication Complexity
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Elements of Information Theory
- Information Equals Amortized Communication
- An Almost Optimal Algorithm for Computing Nonnegative Rank
This page was built for publication: Information-theoretic approximations of the nonnegative rank
