Exponential Separation of Information and Communication for Boolean Functions

DOI10.1145/2746539.2746572zbMath1321.68311OpenAlexW2082224527MaRDI QIDQ5892102

Anat Ganor, Gillat Kol, Ran Raz

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746572

zbMATH Keywords

information complexitycommunication complexitydirect sumamortized communication complexitycommunication compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

Interactive Information Complexity, Interactive Information Complexity, A discrepancy lower bound for information complexity, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Information complexity and applications., Information lower bounds via self-reducibility, On the Communication Complexity of Key-Agreement Protocols.

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming