Information Lower Bounds via Self-reducibility

DOI10.1007/978-3-642-38536-0_16zbMath1345.68153OpenAlexW2268119547MaRDI QIDQ4928483

Mark Braverman, Ankit Garg, Omri Weinstein, Denis Pankratov

Publication date: 14 June 2013

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38536-0_16

Mathematics Subject Classification ID

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

Related Items (6)

The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Common information and unique disjointness ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness

This page was built for publication: Information Lower Bounds via Self-reducibility