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

DOI10.1007/s00453-018-0484-8zbMath1434.68177arXiv1703.07833OpenAlexW3098181265WikidataQ129557345 ScholiaQ129557345MaRDI QIDQ5919672

Suzin You, Yuval Filmus, Hamed Hatami, Yaqiao Li

Publication date: 17 October 2019

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.07833

zbMATH Keywords

information complexityAND functionconcavity conditionmulti-party number-in-hand model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11)

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Information lower bounds via self-reducibility
• An information statistics approach to data stream and communication complexity
• On the distributional complexity of disjointness
• Information Equals Amortized Communication
• Communication Complexity
• Some Results on Distributed Source Coding for Interactive Function Computation
• The Infinite-Message Limit of Two-Terminal Interactive Source Coding
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• From information to exact communication
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping

This page was built for publication: Information complexity of the AND function in the two-party and multi-party settings