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