Two applications of information complexity

DOI10.1145/780542.780640MaRDI QIDQ3581283zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(23)

• The landscape of communication complexity classes
• Trading information complexity for error. II: The case of a large error and the external information complexity
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Communication complexity with small advantage
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Hellinger volume and number-on-the-forehead communication complexity
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Lower bounds on information complexity via zero-communication protocols and applications
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• A stronger LP bound for formula size lower bounds via clique constraints
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• Kolmogorov complexity and combinatorial methods in communication complexity
• Communication Lower Bounds Via the Chromatic Number
• An information statistics approach to data stream and communication complexity
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Memory lower bounds for XPath evaluation over XML streams
• Non-reversible stationary states for majority voter and Ising dynamics on trees
• Distributed distance approximation
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• Approximate degree composition for recursive functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581283)