On randomized one-round communication complexity
From MaRDI portal
Recommendations
Cited in
(46)- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
- Placing conditional disclosure of secrets in the communication complexity universe
- The role of randomness in the broadcast congested clique model
- VC-saturated set systems
- A Sauer-Shelah-Perles lemma for lattices
- Upper and lower bounds on the power of advice
- Frequent directions: simple and deterministic matrix sketching
- Randomized OBDDs for the most significant bit of multiplication need exponential size
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Sample complexity bounds on differentially private learning via communication complexity
- Communication complexity of conditional disclosure of secrets and attribute-based encryption
- Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
- Rounds in Communication Complexity Revisited
- scientific article; zbMATH DE number 1263236 (Why is no real title available?)
- Sign rank versus Vapnik-Chervonenkis dimension
- Foundations of homomorphic secret sharing
- Randomized sliding window algorithms for regular languages
- Streaming Dictionary Matching with Mismatches
- Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
- A compressed classical description of quantum states
- scientific article; zbMATH DE number 7559401 (Why is no real title available?)
- Placing conditional disclosure of secrets in the communication complexity universe
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- Independent sets in vertex-arrival streams
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- Kolmogorov complexity and combinatorial methods in communication complexity
- A little advice can be very helpful
- Derandomization for sliding window algorithms with strict correctness
- An information statistics approach to data stream and communication complexity
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- Optimal One-Pass Nonparametric Estimation Under Memory Constraint
- Space limited linear-time graph algorithms on big data
- Revisiting maximum satisfiability and related problems in data streams
- Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
- Nearly time-optimal kernelization algorithms for the line-cover problem with big data
- A hierarchy of constant communication complexity
- Distributional PAC-learning from Nisan's natural proofs
- Randomized communication and implicit graph representations
- Regular languages in the sliding window model
- Shared versus private randomness in distributed interactive proofs
- Quantum communication complexity of linear regression
- Streaming algorithms for geometric Steiner forest
- Connectivity labeling in faulty colored graphs
- New results for finding common neighborhoods in massive graphs in the data stream model
This page was built for publication: On randomized one-round communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300607)
