Construction of Very Hard Functions for Multiparty Communication Complexity

DOI10.1051/ITA:2000107MaRDI QIDQ4494482zbMATH OpenOpenAlexFDO

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, https://semanticscholar.org/paper/f5914e482983f402fc9dfc1f909edf35aeefab7d

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)

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

Cites work

• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• A Boolean function requiring 3n network size
• Communication Complexity
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Multiparty communication complexity and very hard functions
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Optimal lower bounds on the multiparty communication complexity

Cited in

(2)

• Multiparty communication complexity and very hard functions
• scientific article; zbMATH DE number 1418336 (Why is no real title available?)

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)