Relative Discrepancy Does not Separate Information and Communication Complexity

DOI10.1007/978-3-662-47672-7_41zbMath1440.68090OpenAlexW766978305MaRDI QIDQ3448811

Sophie Laplante, Mathieu Laurière, Lila Fontes, Iordanis Kerenidis, Rahul Jain, Jérémie Roland

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://dipot.ulb.ac.be/dspace/bitstream/2013/206002/3/Fontes2015_Chapter_RelativeDiscrepancyDoesNotSepa.pdf

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Related Items (5)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Interactive Information Complexity ⋮ The landscape of communication complexity classes ⋮ Interactive Information Complexity ⋮ Exponential Separation of Communication and External Information

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• An information statistics approach to data stream and communication complexity
• How to compress interactive communication
• Information Equals Amortized Communication
• Relative Discrepancy Does not Separate Information and Communication Complexity
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• The Communication Complexity of Correlation
• En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
• Exponential separation of communication and external information
• Interactive information complexity
• Exponential Separation of Information and Communication for Boolean Functions

This page was built for publication: Relative Discrepancy Does not Separate Information and Communication Complexity