Exponential separation of information and communication for Boolean functions

DOI10.1145/2907939MaRDI QIDQ5895073zbMATH OpenOpenAlexFDO

Authors Anat Ganor, Gillat Kol, Ran Raz

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

communication complexitydirect sumamortized communication complexityinformation complexitycommunication compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Recommendations

• Exponential Separation of Information and Communication for Boolean Functions
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity

Cited in

(19)

• Relative discrepancy does not separate information and communication complexity
• Trading information complexity for error
• The communication complexity of functions with large outputs
• Exponential separation of communication and external information
• The landscape of communication complexity classes
• Canalizing Boolean Functions Maximize Mutual Information
• A hierarchy of constant communication complexity
• Communication complexity under product and nonproduct distributions
• Simplified separation of information and communication
• Query-to-communication lifting using low-discrepancy gadgets
• Sign rank vs discrepancy
• Information dissemination via broadcasts in the presence of adversarial noise
• Communication and information complexity
• The work of Mark Braverman
• Applications of random algebraic constructions to hardness of approximation
• Exponential Separation of Information and Communication for Boolean Functions
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity
• Lower bounds on information complexity via zero-communication protocols and applications

This page was built for publication: Exponential separation of information and communication for Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895073)