On relations between counting communication complexity classes

DOI10.1016/J.JCSS.2004.03.002zbMATH Open1159.68465OpenAlexW2018302254MaRDI QIDQ1880784FDOQ1880784

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

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

Cited In (5)

• On Toda’s Theorem in Structural Communication Complexity
• 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

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)