Trading information complexity for error. II: The case of a large error and the external information complexity

DOI10.1016/j.ic.2022.104952OpenAlexW2981559244MaRDI QIDQ2105437

Yaqiao Li

Publication date: 8 December 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104952

zbMATH Keywords

information complexityerrorXORANDtrivial distributions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• An information statistics approach to data stream and communication complexity
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• How to Compress Interactive Communication
• Quantum Information Complexity
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Interactive Information Complexity
• Space lower bounds for distance approximation in the data stream model
• Two applications of information complexity
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
• Communication Complexity
• Elements of Information Theory
• From information to exact communication
• An information complexity approach to extended formulations
• Unnamed Item
• Unnamed Item

This page was built for publication: Trading information complexity for error. II: The case of a large error and the external information complexity