Languages with Bounded Multiparty Communication Complexity

DOI10.1007/978-3-540-70918-3_43zbMATH Open1186.68249OpenAlexW1632935999MaRDI QIDQ3590958FDOQ3590958

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• An Algebraic Perspective on Boolean Function Learning
• Title not available (Why is that?)
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• A note on multiparty communication complexity and the Hales-Jewett theorem
• The NOF multiparty communication complexity of composed functions
• Quivers of monoids with basic algebras.
• Complete classifications for the communication complexity of regular languages

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)