The Communication Complexity of Set Intersection and Multiple Equality Testing

DOI10.1137/20M1326040zbMath1462.68058MaRDI QIDQ5858651

Dawei Huang, Zhijun Zhang, Seth Pettie, Yixiang Zhang

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundscommunication complexityset disjointnessdistributed triangle detection

Mathematics Subject Classification ID

Combinatorial probability (60C05) Randomized algorithms (68W20) Communication complexity, information complexity (68Q11)

Related Items (1)

The communication complexity of functions with large outputs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Certifying equality with limited interaction
• A discrepancy lower bound for information complexity
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• On the distributional complexity of disjointness
• The landscape of communication complexity classes
• Towards proving strong direct product theorems
• Detecting cliques in CONGEST networks
• Fooling views: a new lower bound technique for distributed computations under congestion
• How to Compress Interactive Communication
• A strong direct product theorem for disjointness
• Beyond set disjointness
• On the power of the congested clique model
• Information Equals Amortized Communication
• Sparse and Lopsided Set Disjointness via Information Theory
• Communication Complexity (for Algorithm Designers)
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Lower Bounds for Subgraph Detection in the CONGEST Model
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Arboricity and Subgraph Listing Algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Probabilistic Communication Complexity of Set Intersection
• Interactive Information Complexity
• Amortized Communication Complexity
• Communication Complexity
• Amortized Communication Complexity of an Equality Predicate
• Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
• Communication Complexity
• Distributed Triangle Detection via Expander Decomposition
• Triangle Finding and Listing in CONGEST Networks
• An information complexity approach to extended formulations
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: The Communication Complexity of Set Intersection and Multiple Equality Testing