Construction of Very Hard Functions for Multiparty Communication Complexity

DOI10.1051/ITA:2000107zbMATH Open0971.68065OpenAlexW2163596802MaRDI QIDQ4494482FDOQ4494482

Authors: Ján Maňuch 

Publication date: 6 August 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92624

Recommendations

• scientific article; zbMATH DE number 1418336
• Lower bounds on the multiparty communication complexity
• Multiparty communication complexity and very hard functions
• scientific article; zbMATH DE number 1688365
• Optimal lower bounds on the multiparty communication complexity

zbMATH Keywords

multiparty communication model

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Communication Complexity
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• A Boolean function requiring 3n network size
• Title not available (Why is that?)
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Multiparty communication complexity and very hard functions
• Optimal lower bounds on the multiparty communication complexity

Cited In (2)

• Multiparty communication complexity and very hard functions
• Title not available (Why is that?)

This page was built for publication: Construction of Very Hard Functions for Multiparty Communication Complexity

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