A discrepancy lower bound for information complexity

DOI10.1007/s00453-015-0093-8zbMath1353.68088arXiv1112.2000OpenAlexW2113315930MaRDI QIDQ343867

Omri Weinstein, Mark Braverman

Publication date: 29 November 2016

Published in: Algorithmica, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.2000

Mathematics Subject Classification ID

Related Items (14)

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ Unnamed Item ⋮ Information complexity and applications. ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Information lower bounds via self-reducibility ⋮ The communication complexity of addition ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Exponential Separation of Communication and External Information ⋮ Communication Complexity of Statistical Distance ⋮ Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Unnamed Item
• A full proof of the BGW protocol for perfectly secure multiparty computation
• An information statistics approach to data stream and communication complexity
• Quantum and approximate privacy
• On the distributional complexity of disjointness
• Towards proving strong direct product theorems
• How to compress interactive communication
• A strong direct product theorem for disjointness
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Privacy, additional information and communication
• Communication Complexity
• The Communication Complexity of Correlation
• Interactive information complexity
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Information Equals Amortized Communication
• The communication complexity of addition
• A Zero-One Law for Boolean Privacy
• Exponential Separation of Information and Communication for Boolean Functions

This page was built for publication: A discrepancy lower bound for information complexity