Lower bounds for one-way probabilistic communication complexity

DOI10.1007/3-540-56939-1_76MaRDI QIDQ4630264zbMATH OpenOpenAlexFDO

Authors F. 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 functionprobabilistic communicationcommunication complexitycommunication matrix

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Probabilistic communication complexity
• New bounds on classical and quantum one-way communication complexity
• Different Modes of Communication
• scientific article; zbMATH DE number 4068270

Cites work

• scientific article; zbMATH DE number 17834 (Why is no real title available?)
• scientific article; zbMATH DE number 3531303 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• Different Modes of Communication
• Information Transfer under Different Sets of Protocols
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Lower bounds on communication complexity
• Probabilistic automata
• Probabilistic communication complexity
• Results on communication complexity classes
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(9)

• Communication lower bounds using directional derivatives
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• Probabilistic communication complexity
• Lower bounds on the probability of successful substitution of messages
• Probabilistic communication complexity over the reals
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• New bounds on classical and quantum one-way communication complexity
• A linear lower bound on the unbounded error probabilistic communication complexity.

This page was built for publication: Lower bounds for one-way probabilistic communication complexity

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