A candidate for a strong separation of information and communication

DOI10.4230/LIPICS.ITCS.2018.11MaRDI QIDQ4993274zbMATH OpenFDO

Authors Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2018.11

zbMATH Keywords

amortized communication complexitycommunication complexitycommunication compressiondirect suminformation complexity

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Recommendations

• Exponential separation of communication and external information
• Exponential separation of communication and external information
• Interactive compression for product distributions
• Compressing interactive communication under product distributions
• Interactive compression to external information

Cites work

• An information statistics approach to data stream and communication complexity
• Coding for computing
• Communication Complexity
• Exponential separation of communication and external information
• How to compress interactive communication
• Information Equals Amortized Communication
• Interactive compression for product distributions
• Interactive information complexity
• Lower bounds in communication complexity
• Lower bounds on information complexity via zero-communication protocols and applications
• Two-way source coding with a fidelity criterion

Cited in

(2)

• Exponential separation of communication and external information
• The work of Mark Braverman

This page was built for publication: A candidate for a strong separation of information and communication

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