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

amortized communication complexitycommunication complexitycommunication compressiondirect suminformation complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

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)

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

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)