Information lower bounds via self-reducibility

DOI10.1007/s00224-015-9655-zzbMath1356.68086OpenAlexW200600406MaRDI QIDQ504999

Denis Pankratov, Ankit Garg, Mark Braverman, Omri Weinstein

Publication date: 18 January 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-015-9655-z

zbMATH Keywords

inner productinformation complexitycommunication complexitygap-Hamming distanceself-reducibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Unnamed Item ⋮ Information complexity of the AND function in the two-party and multi-party settings

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• A discrepancy lower bound for information complexity
• An information statistics approach to data stream and communication complexity
• Quantum and approximate privacy
• How to compress interactive communication
• The Hardness of Being Private
• Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Communication Complexity
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Interactive information complexity
• Information Equals Amortized Communication
• From information to exact communication
• An information complexity approach to extended formulations
• A Method for the Construction of Minimum-Redundancy Codes
• Exponential Separation of Information and Communication for Boolean Functions

This page was built for publication: Information lower bounds via self-reducibility