The Probabilistic Communication Complexity of Set Intersection
From MaRDI portal
Publication:4030193
DOI10.1137/0405044zbMath0760.68040OpenAlexW1980223785MaRDI QIDQ4030193
Bala Kalyanasundaram, Georg Schnitger
Publication date: 1 April 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0405044
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Related Items
Efficient set intersection with simulation-based security, The Simultaneous Communication of Disjointness with Applications to Data Streams, Approximation Limits of Linear Programs (Beyond Hierarchies), Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models, Interactive Information Complexity, The communication complexity of the Hamming distance problem, Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption, Communication Lower Bounds via Critical Block Sensitivity, Memory lower bounds of reductions revisited, Interactive Information Complexity, Certifying equality with limited interaction, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness, Evaluating Bayesian Networks via Data Streams, A note on efficient aggregate queries in sensor networks, An information statistics approach to data stream and communication complexity, Fourier analysis for probabilistic communication complexity, Lower Bounds for Subgraph Detection in the CONGEST Model, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Distributed Testing of Distance-k Colorings, Around the log-rank conjecture, Communication costs in a geometric communication network, 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, Unnamed Item, The unbounded-error communication complexity of symmetric functions, Arithmetic sketching, A distributed algorithm for directed minimum-weight spanning tree, The work of Mark Braverman, Communication and information complexity, Query-to-Communication Lifting for BPP, Unnamed Item, Unnamed Item, Single-pass streaming algorithms to partition graphs into few forests, Hash challenges: stretching the limits of compare-by-hash in distributed data deduplication, Generalizations of the distributed Deutsch–Jozsa promise problem, On a theorem of Razborov, Distributed Graph Algorithms and their Complexity: An Introduction, Detecting cliques in CONGEST networks, Foundations of Homomorphic Secret Sharing, Matrix rank and communication complexity, Information complexity and applications., Quantum lower bounds by quantum arguments, String Matching: Communication, Circuits, and Learning., An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, Comparing two sets without disclosing them, Non-interactive proofs of proximity, On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity, Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, Property testing lower bounds via communication complexity, On the power of randomized multicounter machines, Finding longest increasing and common subsequences in streaming data, On the existence of Pareto efficient and envy-free allocations, Unnamed Item, Unnamed Item, Unnamed Item, On probabilistic pushdown automata, A stable marriage requires communication, The communication complexity of enumeration, elimination, and selection, Unnamed Item, Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy, Correlation clustering in data streams, Exponential separation of quantum and classical online space complexity, Nondeterministic and randomized Boolean hierarchies in communication complexity, Superlinear Advantage for Exact Quantum Algorithms, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, Choosing, agreeing, and eliminating in communication complexity, Extended formulations, nonnegative factorizations, and randomized communication protocols, 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, The Complexity of Data Aggregation in Directed Networks, Equality alone does not simulate randomness, Random resolution refutations, Verifiable Stream Computation and Arthur--Merlin Communication, Fooling Pairs in Randomized Communication Complexity, Unnamed Item, Unnamed Item, The Communication Complexity of Set Intersection and Multiple Equality Testing, The complexity of quantum disjointness, Exponential Separation of Communication and External Information, On the P versus NP intersected with co-NP question in communication complexity, Communication Lower Bounds Using Directional Derivatives, Resolution over linear equations modulo two, The space complexity of approximating the frequency moments, Quantum communication and complexity., Unnamed Item, On graph problems in a semi-streaming model, Unnamed Item, Upper bounds on communication in terms of approximate rank, On the streaming indistinguishability of a random permutation and a random function
