Relative Discrepancy Does not Separate Information and Communication Complexity

DOI10.1007/978-3-662-47672-7_41zbMath1440.68090MaRDI 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

68Q11: Communication complexity, information complexity

Related Items

Interactive Information Complexity, The landscape of communication complexity classes, Relative Discrepancy Does not Separate Information and Communication Complexity, Interactive Information Complexity

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