Lower bounds for one-way probabilistic communication complexity

DOI10.1007/3-540-56939-1_76zbMATH Open1418.68097OpenAlexW1590593970MaRDI QIDQ4630264FDOQ4630264

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

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

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)

Cites Work

• Probabilistic automata
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Title not available (Why is that?)
• Probabilistic communication complexity
• Lower bounds on communication complexity
• Title not available (Why is that?)
• Results on communication complexity classes
• Information Transfer under Different Sets of Protocols
• Title not available (Why is that?)
• Title not available (Why is that?)
• Different Modes of Communication

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
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Lower bounds for one-way probabilistic communication complexity and their application to space 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)