Multiparty communication complexity of finite monoids

MaRDI QIDQ4942276zbMATH OpenFDO

Authors Jean-François Raymond, Pascal Tesson, Denis Thérien

Publication date 21 March 2000

zbMATH Keywords

complexity of languagesYao's two-party communication game

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1688365
• Lower bounds on the multiparty communication complexity
• The multiparty communication complexity of set disjointness
• The multiparty communication complexity of set disjointness
• Multiparty communication complexity and very hard functions
• Optimal lower bounds on the multiparty communication complexity
• Multiparty communication complexity of vector-valued and sum-type functions
• Separating deterministic from randomized multiparty communication complexity
• A separation of NP and conp in multiparty communication complexity

Cited in

(2)

• Languages with Bounded Multiparty Communication Complexity
• When can one finite monoid simulate another?

This page was built for publication: Multiparty communication complexity of finite monoids

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