On relations between counting communication complexity classes

DOI10.1016/j.jcss.2004.03.002zbMath1159.68465MaRDI QIDQ1880784

Christoph Meinel, Stephan Waack, Carsten Damm, Matthias Krause

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 bound; Lower bound; Modularity; Non-determinism; Protocol; Communication complexity class; Probabilism

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68M12: Network protocols

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of small-depth threshold circuits
• Relations between communication complexity classes
• On oblivious branching programs of linear length
• Meanders and their applications in lower bounds arguments
• Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Non-deterministic communication complexity with few witnesses
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• Relativized counting classes: Relations among thresholds, parity, and mods
• Complexity classes defined by counting quantifiers
• On the power of generalized Mod-classes
• Communication Complexity