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)

Review text

We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established

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)