Languages with Bounded Multiparty Communication Complexity

DOI10.1007/978-3-540-70918-3_43MaRDI QIDQ3590958zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, A. Krebs, Michal Koucký, Pascal Tesson, Denis Thérien, Mario Szegedy

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70918-3_43

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds on the multiparty communication complexity
• scientific article; zbMATH DE number 1419257
• Optimal lower bounds on the multiparty communication complexity
• Multiparty communication complexity and very hard functions
• Communication Complexity and Lower Bounds on Multilective Computations
• scientific article; zbMATH DE number 1418336
• scientific article; zbMATH DE number 1688365
• A separation of NP and conp in multiparty communication complexity
• On the Non-deterministic Communication Complexity of Regular Languages

Cited in

(7)

• The NOF multiparty communication complexity of composed functions
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• Quivers of monoids with basic algebras.
• scientific article; zbMATH DE number 1962802 (Why is no real title available?)
• A note on multiparty communication complexity and the Hales-Jewett theorem
• Complete classifications for the communication complexity of regular languages
• An Algebraic Perspective on Boolean Function Learning

This page was built for publication: Languages with Bounded Multiparty Communication Complexity

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