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

Communication complexity classLower boundModularityNon-determinismProbabilismProtocolUpper bound

Mathematics Subject Classification ID

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

Cites work

• 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
• 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?)
• 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)

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

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)