Separating counting communication complexity classes

DOI10.1007/3-540-55210-3_190MaRDI QIDQ5096788zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack

Publication date 18 August 2022

Published in STACS 92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55210-3_190

zbMATH Keywords

communication complexitycomplexity of Boolean functionsdistributed computinglower bound argumentsprobabilismseparation of complexity classes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The landscape of communication complexity classes
• The landscape of communication complexity classes
• scientific article; zbMATH DE number 1256663
• Results on communication complexity classes
• Counting classes: Thresholds, parity, mods, and fewness

Cites work

• scientific article; zbMATH DE number 4213443 (Why is no real title available?)
• scientific article; zbMATH DE number 17548 (Why is no real title available?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• NP is as easy as detecting unique solutions
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

Cited in

(5)

• Results on communication complexity classes
• Lower bounds for linearly transformed OBDDs and FBDDs
• The landscape of communication complexity classes
• The landscape of communication complexity classes
• Lower bounds for the modular communication complexity of various graph accessibility problems

This page was built for publication: Separating counting communication complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096788)