On randomized one-round communication complexity

DOI10.1007/s000370050018zbMath0942.68059OpenAlexW2089797683MaRDI QIDQ1300607

Noam Nisan, Dana Ron, Ilan Kremer

Publication date: 1 September 1999

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050018

zbMATH Keywords

randomized one-round communication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (35)

Communication with contextual uncertainty ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ⋮ VC-saturated set systems ⋮ Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption ⋮ Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Triangle counting in dynamic graph streams ⋮ An information statistics approach to data stream and communication complexity ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ Optimal One-Pass Nonparametric Estimation Under Memory Constraint ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Unnamed Item ⋮ Space limited linear-time graph algorithms on big data ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ Unnamed Item ⋮ Foundations of Homomorphic Secret Sharing ⋮ New results for finding common neighborhoods in massive graphs in the data stream model ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Derandomization for sliding window algorithms with strict correctness ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ The role of randomness in the broadcast congested clique model ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Streaming Dictionary Matching with Mismatches ⋮ Unnamed Item ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs

This page was built for publication: On randomized one-round communication complexity