Lower bounds for the modular communication complexity of various graph accessibility problems

DOI10.1007/3-540-59175-3_107zbMath1495.68083OpenAlexW1574848776MaRDI QIDQ5096349

Christoph Meinel, Stephan Waack

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_107

zbMATH Keywords

computational complexityGAPprojection reductionsmodular communication protocolsvariation ranks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Modified branching programs and their computational power
• Relationships between nondeterministic and deterministic tape complexities
• Languages that Capture Complexity Classes
• Separating counting communication complexity classes

This page was built for publication: Lower bounds for the modular communication complexity of various graph accessibility problems