The Probabilistic Communication Complexity of Set Intersection
From MaRDI portal
Recommendations
- Deterministic communication complexity of set intersection
- The communication complexity of set intersection and multiple equality testing
- The communication complexity of set intersection and multiple equality testing
- Beyond set disjointness: the communication complexity of finding the intersection
- Communication complexity of set-disjointness for all probabilities
- scientific article; zbMATH DE number 6696541
- The randomized communication complexity of set disjointness
- The communication complexity of the inevitable intersection problem
- The multiparty communication complexity of set disjointness
- The multiparty communication complexity of set disjointness
Cited in
(only showing first 100 items - show all)- On the P versus NP intersected with co-NP question in communication complexity
- The communication complexity of interval orders
- The space complexity of approximating the frequency moments
- Still another rank determination of set intersection matrices with an application in communication complexity
- Memory lower bounds of reductions revisited
- Information complexity and applications.
- Non-interactive proofs of proximity
- On the power of randomized multicounter machines
- Quantum communication and complexity.
- Deterministic communication complexity of set intersection
- Fourier analysis for probabilistic communication complexity
- Matrix rank and communication complexity
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- On the existence of Pareto efficient and envy-free allocations
- Correlation clustering in data streams
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Upper bounds on communication in terms of approximate rank
- On the streaming indistinguishability of a random permutation and a random function
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Detecting cliques in CONGEST networks
- Probabilistic communication complexity over the reals
- A stable marriage requires communication
- Random resolution refutations
- Resolution over linear equations modulo two
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- The unbounded-error communication complexity of symmetric functions
- Finding longest increasing and common subsequences in streaming data
- On graph problems in a semi-streaming model
- A distributed algorithm for directed minimum-weight spanning tree
- Single-pass streaming algorithms to partition graphs into few forests
- Efficient set intersection with simulation-based security
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- Superlinear advantage for exact quantum algorithms
- Communication complexity of set-disjointness for all probabilities
- Upper and lower bounds on the power of advice
- The multiparty communication complexity of set disjointness
- The effect of range and bandwidth on the round complexity in the congested clique model
- Fooling pairs in randomized communication complexity
- scientific article; zbMATH DE number 6696541 (Why is no real title available?)
- Generalizations of the distributed Deutsch-Jozsa promise problem
- On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
- The complexity of data aggregation in directed networks
- Evaluating Bayesian networks via data streams
- Lower bounds for subgraph detection in the CONGEST model
- Certifying equality with limited interaction
- The Simultaneous Communication of Disjointness with Applications to Data Streams
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Interactive Information Complexity
- Communication complexity of conditional disclosure of secrets and attribute-based encryption
- scientific article; zbMATH DE number 3911705 (Why is no real title available?)
- Hash challenges: stretching the limits of compare-by-hash in distributed data deduplication
- On a theorem of Razborov
- Communication lower bounds via critical block sensitivity
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- Trading information complexity for error
- Interactive information complexity
- Simplified separation of information and communication
- Separation of unbounded-error models in multi-party communication complexity
- Multiparty quantum communication complexity of triangle finding
- scientific article; zbMATH DE number 894723 (Why is no real title available?)
- The communication complexity of the inevitable intersection problem
- Foundations of homomorphic secret sharing
- Exponential separation of communication and external information
- Lower bounds for approximating graph parameters via communication complexity
- Communication complexity of correlated equilibrium with small support
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- Detecting cliques in CONGEST networks
- Streaming algorithms for planar convex hulls
- Equality alone does not simulate randomness
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Distributed Testing of Distance-k Colorings
- The complexity of quantum disjointness
- Query-to-communication lifting for BPP
- Distributed graph algorithms and their complexity: an introduction
- Verifiable stream computation and Arthur-Merlin communication
- Communication lower bounds using directional derivatives
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- The communication complexity of set intersection and multiple equality testing
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- String Matching: Communication, Circuits, and Learning.
- Quantum lower bounds by quantum arguments
- The communication complexity of enumeration, elimination, and selection
- An information statistics approach to data stream and communication complexity
- Around the log-rank conjecture
- Communication costs in a geometric communication network
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Fine-grained complexity lower bounds for problems in computer aided verification
- Secure sampling with sublinear communication
- The communication complexity of functions with large outputs
- Bounds on oblivious multiparty quantum communication complexity
- Arithmetic sketching
- The work of Mark Braverman
- Communication and information complexity
- The communication complexity of pointer chasing: applications of entropy and sampling
- Constructive separations and their consequences
- Upper bounds on communication in terms of approximate rank
- Communication complexity of discrete fair division
- Lower bounds for semi-adaptive data structures via corruption
This page was built for publication: The Probabilistic Communication Complexity of Set Intersection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4030193)
