Fractional Covers and Communication Complexity

DOI10.1137/S0895480192238482zbMath0817.68094OpenAlexW2010730726MaRDI QIDQ4764345

Noam Nisan, Eyal Kushilevitz, Mauricio Karchmer

Publication date: 10 July 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480192238482

zbMATH Keywords

communication complexityinteger programming problem

Mathematics Subject Classification ID

Linear programming (90C05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Information theory (general) (94A15) Source coding (94A29)

Related Items (17)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ The rectangle covering number of random Boolean matrices ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Upper bounds on the Boolean rank of Kronecker products ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Unnamed Item ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ On convex complexity measures ⋮ Information-theoretic approximations of the nonnegative rank ⋮ On derandomized composition of Boolean functions ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Lifting Theorems for Equality ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ On covering graphs by complete bipartite subgraphs

This page was built for publication: Fractional Covers and Communication Complexity