Two applications of information complexity

DOI10.1145/780542.780640zbMath1192.68297MaRDI 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

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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