A discrepancy lower bound for information complexity

DOI10.1007/978-3-642-32512-0_39zbMath1353.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

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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