On relations between counting communication complexity classes

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

Stephan Waack, Carsten Damm, Christoph Meinel, 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 boundLower boundModularityNon-determinismProtocolCommunication complexity classProbabilism

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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