Lower bounds for one-way probabilistic communication complexity and their application to space complexity

DOI10.1016/0304-3975(95)00157-3zbMath0871.68009OpenAlexW2027214648WikidataQ62045251 ScholiaQ62045251MaRDI QIDQ1351496

Farid M. Ablayev

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00157-3

zbMATH Keywords

deterministic communication complexityboolean functionsprobabilistic communication characteristic

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Hellinger volume and number-on-the-forehead communication complexity ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Interactive Information Complexity ⋮ Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption ⋮ Interactive Information Complexity ⋮ Certifying equality with limited interaction ⋮ An information statistics approach to data stream and communication complexity ⋮ Randomization and nondeterminism are comparable for ordered read-once branching programs ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ Unnamed Item ⋮ Lower bounds for one-way probabilistic communication complexity ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Unnamed Item ⋮ Correlation clustering in data streams ⋮ Exponential separation of quantum and classical online space complexity ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity

Cites Work

• Probabilistic communication complexity
• Results on communication complexity classes
• Majority gates vs. general weighted threshold gates
• Information Transfer under Different Sets of Protocols
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Rounds in Communication Complexity Revisited
• Computational Complexity of Probabilistic Turing Machines
• Lower bounds for one-way probabilistic communication complexity
• Probabilistic automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item