Two applications of information complexity

DOI10.1145/780542.780640zbMath1192.68297OpenAlexW2070053775MaRDI QIDQ3581283

T. S. Jayram, Ravi Kumar, D. Sivakumar

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780640

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (18)

Hellinger volume and number-on-the-forehead communication complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ An information statistics approach to data stream and communication complexity ⋮ Communication complexity with small advantage ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Memory lower bounds for XPath evaluation over XML streams ⋮ Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity

This page was built for publication: Two applications of information complexity