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

(16)

• The communication complexity of functions with large outputs
• Trading information complexity for error
• 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
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity
• Communication complexity under product and nonproduct distributions
• Communication and information complexity
• The work of Mark Braverman
• Query-to-communication lifting using low-discrepancy gadgets
• The landscape of communication complexity classes
• Canalizing Boolean Functions Maximize Mutual Information
• Sign rank vs discrepancy
• Simplified separation of information and communication
• Exponential Separation of Information and Communication for Boolean Functions

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)