On relations between counting communication complexity classes

DOI10.1016/J.JCSS.2004.03.002MaRDI QIDQ1880784zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack

Publication date 1 October 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.03.002

zbMATH Keywords

Upper boundLower boundModularityNon-determinismProtocolCommunication complexity classProbabilism

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Cites work

• scientific article; zbMATH DE number 3970935 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)
• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
• Communication Complexity
• Complexity classes defined by counting quantifiers
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• Meanders and their applications in lower bounds arguments
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Non-deterministic communication complexity with few witnesses
• On oblivious branching programs of linear length
• On the power of generalized Mod-classes
• On the power of small-depth threshold circuits
• Relations between communication complexity classes
• Relativized counting classes: Relations among thresholds, parity, and mods

Cited in

(5)

• On Toda’s Theorem in Structural Communication Complexity
• The landscape of communication complexity classes
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• On approximation by \(^{\oplus}\)-OBDDs
• On a theorem of Razborov

This page was built for publication: On relations between counting communication complexity classes

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