Lower bounds for one-way probabilistic communication complexity

DOI10.1007/3-540-56939-1_76zbMath1418.68097OpenAlexW1590593970MaRDI QIDQ4630264

Farid M. Ablayev

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_76

zbMATH Keywords

Boolean functioncommunication complexityprobabilistic communicationcommunication matrix

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)

Related Items

Lower bounds for one-way probabilistic communication complexity and their application to space complexity, A lower bound for integer multiplication on randomized ordered read-once branching programs.

Cites Work

• Probabilistic communication complexity
• Lower bounds on communication complexity
• Results on communication complexity classes
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Different Modes of Communication
• Information Transfer under Different Sets of Protocols
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Probabilistic automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item