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

DOI10.1016/J.IC.2022.104952OpenAlexW2981559244MaRDI QIDQ2105437FDOQ2105437

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

errorinformation complexityXORANDtrivial distributions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Elements of Information Theory
• Communication Complexity
• Lower bounds for one-way probabilistic communication complexity and their application to space 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
• An information statistics approach to data stream and communication complexity
• An information complexity approach to extended formulations
• How to compress interactive communication
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Interactive Information Complexity
• From information to exact communication
• Quantum Information Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Trading information complexity for error II: the case of a large error and external information complexity
• Title not available (Why is that?)

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

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