Common information and unique disjointness

DOI10.1007/s00453-016-0132-0zbMath1353.68072OpenAlexW2291562724MaRDI QIDQ343843

Gábor Braun, Sebastian Pokutta

Publication date: 29 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0132-0

zbMATH Keywords

information theorycommon informationextended formulationsextension complexitynonnegative rankcorrelation polytopeunique disjointness

Mathematics Subject Classification ID

Linear programming (90C05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ Extension Complexity of Independent Set Polytopes ⋮ Affine reductions for LPs and SDPs ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ On the existence of 0/1 polytopes with high semidefinite extension complexity ⋮ Uncapacitated flow-based extended formulations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially

Cites Work

• An information statistics approach to data stream and communication complexity
• Extended formulations for polygons
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• On the extension complexity of combinatorial polytopes
• Expressing combinatorial optimization problems by linear programs
• On the distributional complexity of disjointness
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial bounds on nonnegative rank and extended formulations
• Information-theoretic approximations of the nonnegative rank
• An upper bound for nonnegative rank
• Some \(0/1\) polytopes need exponential size extended formulations
• A note on the extension complexity of the knapsack polytope
• Quantum strategic game theory
• Average Case Polyhedral Complexity of the Maximum Stable Set Problem
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Divergence measures based on the Shannon entropy
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• 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
• Information Lower Bounds via Self-reducibility
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• The matching polytope does not admit fully-polynomial size relaxation schemes
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Linear vs. semidefinite extended formulations
• Computing a nonnegative matrix factorization -- provably
• Elements of Information Theory
• From information to exact communication
• An information complexity approach to extended formulations
• On Polyhedral Approximations of the Second-Order Cone
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• Extended formulations in combinatorial optimization

This page was built for publication: Common information and unique disjointness