Separating counting communication complexity classes

DOI10.1007/3-540-55210-3_190zbMath1493.68149OpenAlexW1510339650MaRDI QIDQ5096788

Carsten Damm, Christoph Meinel, Stephan Waack, Matthias Krause

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

distributed computingcommunication complexityprobabilismcomplexity of Boolean functionsseparation of complexity classeslower bound arguments

Mathematics Subject Classification ID

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

Related Items

Lower bounds for the modular communication complexity of various graph accessibility problems ⋮ Lower bounds for linearly transformed OBDDs and FBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines