The Communication Complexity of Set Intersection and Multiple Equality Testing

Dawei Huang; Seth Pettie; Yixiang Zhang; Zhijun Zhang

The Communication Complexity of Set Intersection and Multiple Equality Testing

T0 review · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves a three-way tradeoff: in r rounds, equality testing with error $2^{-E}$ needs $\Omega(E k^{1/r})$ bits, and protocols nearly matching it exist.

desk verdict A serious three-way tradeoff result that looks right: the lower bound is new and the protocols match it in most regimes, with only a modest gap for mid-range rounds. read the letter →

arxiv 1908.11825 v2 pith:I7WA3URP submitted 2019-08-30 cs.IT cs.CCmath.IT

Dawei Huang , Seth Pettie , Yixiang Zhang , Zhijun Zhang This is my paper · ORCID

classification cs.ITcs.CCmath.IT MSC 68Q1794A15

keywords communicationcomplexityequalitytestingsetintersectionrounderrorprobabilitylowerboundsCONGESTmodeltriangleenumeration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a three-way tradeoff between rounds, communication, and error probability for fundamental two-party problems: EqualityTesting, ExistsEqual, SetIntersection, and SetDisjointness. Its main lower bound says that any $r$-round randomized protocol that errs with probability at most $2^{-E}$ on length-$k$ vectors must transmit $\Omega(E k^{1/r})$ bits, and the same bound holds whether the task is to report every coordinate where the vectors agree or merely whether one such coordinate exists. Prior work mostly optimized rounds against communication at a fixed error probability, but this paper treats error as an independent parameter and shows no protocol can simultaneously achieve $O(k+E)$ communication, $O(\log^* k)$ rounds, and error $2^{-E}$ when $E\ge k$. The paper also supplies matching or nearly matching protocols, including protocols that reach optimal $O(k+E)$ communication in $O(\log k)$ rounds, and a distributed triangle-enumeration algorithm running in $O(\Delta/\log n + \log\log\Delta)$ rounds.

What carries the argument

The load-bearing mechanism is the round-by-round invariant, stated as Invariant 3.3. After each round $j$, it asserts that there is a coordinate set $I_j$ of size $k^{1-j/r}$ such that the sender's and receiver's conditional input distributions are pointwise close on $I_j$, and every sub-block of $I_j$ still has entropy close to its original value minus the information revealed so far. The proof alternates two operations: it selects messages and a sub-block that reveal only average information, then filters the input distribution by removing points of tiny probability and points whose probability grew too much relative to the previous round. The error-transfer step, Lemma 3.7, bounds the pointwise ratio between the modified and previous distributions by $2^{\gamma_j+1}$, so an error after round $j$ is at least $2^{-\gamma_j-1}$ times the corresponding error before round $j$, and chaining these ratios backward turns a final error probability of about $1/(4t)$ into an initial error greater than $2^{-E}$. On the upper-bound side, the same machinery includes inner-product tests, the coloring-based test-bit exchange of [FKNN95], and an adversary ``error budget'' that charges communication per false positive.

What would settle it

For example, a 2-round randomized protocol for EqualityTesting on length-$k$ vectors with failure probability $2^{-k}$ and $o(k^{3/2})$ communication would falsify Theorem 2, because the theorem requires $\Omega(k^{3/2})$ bits when $r=2$ and $E=k$.

Watch

Extended reading notes

Core claim

The central claim is a new lower bound: any $r$-round randomized protocol for EqualityTesting or ExistsEqual on vectors of length $k$ with failure probability $p_{\mathrm{err}} = 2^{-E}$ requires $\Omega(E k^{1/r})$ bits of communication. The proof works distributionally, assuming both inputs are uniform over a large alphabet and then tracking what the transcript reveals. It maintains, after each round $j$, a shrinking coordinate set $I_j$ of size $k^{1-j/r}$ on which the two parties' input distributions remain pointwise close and still carry high entropy, so that any error committed at the end can be propagated backward to the initial uniform distribution. The backward propagation shows the protocol must err with probability greater than $2^{-E}$ unless the total communication is $\Omega(E k^{1/r})$. Complementing the lower bound, the paper proves deterministic reductions making SetIntersection equivalent to EqualityTesting up to one round and $O(k+\log\log p_{\mathrm{err}}^{-1})$ bits, and gives protocols achieving $O(k+E k^{1/r})$ communication for ExistsEqual for every $r$, for EqualityTesting when $r=O(1)$ or $r=\Omega(\log k)$, and within an $O(\log r)$ factor otherwise.

Load-bearing premise

The lower-bound proof assumes that after every round the invariant holds: there is still a block of coordinates on which the two parties' input distributions are pointwise close and carry high conditional entropy, and the ratio between the modified and previous distributions is at most $2^{\gamma_j+1}$; if the invariant or that ratio bound fails at any round, the distributional error does not transfer back to the initial uniform distribution.

Editorial extensions

If this is right

If the central lower bound is correct, any protocol that achieves optimal $O(k+E)$ communication for EqualityTesting when $E\ge k$ must use $\Omega(\log k)$ rounds, so the $O(\log^* k)$-round protocols of earlier work cannot simultaneously achieve optimal error and communication.
The deterministic reductions of Theorem 1 transfer the three-way tradeoff to SetIntersection and SetDisjointness, with one extra round in the direction from equality testing to set intersection.
The matching upper bounds show the lower bound is tight for ExistsEqual for every $r$, and for EqualityTesting at the extremes $r=O(1)$ and $r=\Omega(\log k)$; in the intermediate range the gap is at most an $O(\log r)$ factor.
In the CONGEST model, the paper's protocols give local triangle enumeration in $O(\Delta/\log n + \log\log\Delta)$ rounds with high probability, which is optimal for every $\Delta = \Omega(\log n\log\log\log n)$.
By Theorem 1, the upper bounds for EqualityTesting and ExistsEqual imply SetIntersection and SetDisjointness protocols with the same communication volume and one additional round.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The round-by-round conditioning technique looks portable: it may yield a direct proof of the previous round-communication tradeoff for constant error without round elimination, and it may extend to other sparse problems where inputs are long but few coordinates matter.
The residual gap between EqualityTesting and ExistsEqual for $r$ between $\omega(1)$ and $o(\log k)$ suggests a genuine complexity separation, with SetIntersection potentially harder than SetDisjointness in the low-error regime; the paper leaves this as an open problem.
For distributed computing, the lower bound implies that reducing per-instance error on every edge of a graph cannot be done by off-the-shelf SetIntersection protocols; a global algorithm must exploit correlations between instances, exactly as the triangle-enumeration protocol does, or pay an extra $\Delta^{1/r}$ factor.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The thing to know: this paper settles a question that was genuinely open — whether you can simultaneously get O(k+E) communication and O(log* k) rounds for EqualityTesting and related problems. It answers no, with a clean parameterized lower bound Ω(Ek^{1/r}) for r-round protocols with error 2^{-E}. The lower bound is the real meat, and it looks correct. I went through the invariant-based proof with some care, particularly the recursive error transfer in Lemma 3.7. The subtle point is that distributions are updated in sender/receiver order, not fixed Alice/Bob order, and the stress-test note confirms the argument works under that reading. I agree: no load-bearing flaw found.

What's new: prior work (ST13, BCK+16) fixed error probability or treated it only implicitly; here E is an independent parameter, and the resulting tradeoff is the first of its kind. The upper bounds are also substantial: four distinct protocols, including the history-check technique in Section 4.4 that removes the factor r for EqualityTesting with O(r) rounds, and the dimension reduction of Theorem 8. The CONGEST triangle enumeration result in Section 5 is a nice application and is optimal in the stated regimes. The paper is clearly written, and the authors are honest about where their bounds leave a gap: for EqualityTesting with r between ω(1) and o(log k), they only get within a log r factor of their lower bound. That is a real but clearly labeled limitation, not a hidden one.

Soft spots are mostly of the "dense and hard to verify" kind. The proof of the lower bound is intricate; I did not check every constant in every lemma, and a referee should expect to spend real time on Section 3. The upper bound protocols, especially Theorem 12's adaptive estimation, have many moving parts and would benefit from a fuller proof or at least more intuition in places. No code or machine-checked proofs, which is normal for this area. The citation pattern looks fine — prior work is credited, and the reduction in Theorem 1 is an original deterministic alternative to Brody et al.'s randomized one.

Bottom line: this deserves a serious referee. It is a real result for communication complexity and distributed algorithms, and it was already peer-reviewed at SODA. I would cite it and would bring it to reading group. My recommendation is to engage with it as an accept, with the expectation that the referee reports will focus on verifying the invariant analysis and the constants in the protocols.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is a first-principles distributional argument and the upper bounds are explicit protocol constructions.

full rationale

The paper's central lower bound (Theorems 2 and 3) is proved by assuming an r-round protocol with communication c'Ek^{1/r}, defining a hard uniform distribution over [t]^k, and inductively maintaining Invariant 3.3. The invariant is not assumed as a conclusion; it is established by Lemmas 3.4, 3.5, and 3.6 from the predecessor invariant and elementary information-theoretic inequalities. The final error calculation in Lemmas 3.8 and 3.9 derives a contradiction from the assumed small communication, using a round-by-round backward error transfer (Lemma 3.7) that follows from the explicit construction of \hat D^{(j)} and the pointwise ratio bound in Eqn. (3). No parameter is fitted to the quantity being predicted: the lower bound holds for all protocols of the stated communication, rounds, and error, and the proof never uses the desired lower bound as an input. The upper bounds (Theorems 4-7, 9-12) are concrete protocols with explicit communication and error analyses; they do not assume the lower bound. The reduction in Theorem 1 relies on standard perfect-hashing schemes (FKS84, SS90) and is not circular. Self-citations, e.g., to the SODA extended abstract [HPZZ20], are bibliographic and not load-bearing for any derivation. There is no renaming of a known result as a new one, no imported uniqueness theorem, and no ansatz smuggled in via citation. The manuscript is self-contained against external benchmarks, and the only delicate step, the sender/receiver-ordered reading of the round-by-round distributions, is internally consistent with the definitions of D^{(j)}, \hat D^{(j)}, and the message-distribution update. Accordingly, no circular reasoning is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No data-fitted parameters exist in this theoretical work. The proofs rely on standard results: Yao's minimax principle, entropy subadditivity, Chernoff bounds, and succinct perfect hashing, all of which are cited. The hard distribution is a proof construction rather than an unverified axiom.

assumptions (4)

standard math Yao's minimax principle
Used in Section 3 to convert a distributional lower bound on the uniform distribution into a worst-case randomized communication lower bound. Stated as Lemma 2.2.
standard math Subadditivity of joint entropy
Stated as Fact 2.1 and used throughout the lower bound proof to relate the entropy of a joint distribution to the entropies of its coordinates.
standard math Chernoff bound
Stated as Fact 4.3 and used in the analysis of the dimension reduction protocol (Theorem 8) and other concentration arguments.
standard math Existence of succinct perfect hash functions
Used in Appendix A (Theorem 1) to reduce SetIntersection to EqualityTesting deterministically, citing FKS84 and SS90 for O(k + log log |U|)-bit descriptions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Communication Complexity of Set Intersection and Multiple Equality Testing." pith.science (2026). https://pith.science/paper/I7WA3URP

@misc{pith2026190811825,
  author       = {Pith},
  title        = {Pith review of: The Communication Complexity of Set Intersection and Multiple Equality Testing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I7WA3URP}},
  note         = {Machine review of arXiv:1908.11825}
}

abstract

In this paper we explore fundamental problems in randomized communication complexity such as computing Set Intersection on sets of size $k$ and Equality Testing between vectors of length $k$. Sa\u{g}lam and Tardos and Brody et al. showed that for these types of problems, one can achieve optimal communication volume of $O(k)$ bits, with a randomized protocol that takes $O(\log^* k)$ rounds. Aside from rounds and communication volume, there is a \emph{third} parameter of interest, namely the \emph{error probability} $p_{\mathrm{err}}$. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send $\Omega(k + \log p_{\mathrm{err}}^{-1})$ bits. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k + \log p_{\mathrm{err}}^{-1})$ communication and $O(\log^* k)$ rounds? In this paper we prove that there is no universally optimal algorithm, and complement the existing round-communication tradeoffs with a new tradeoff between rounds, communication, and probability of error. In particular: 1. Any protocol for solving Multiple Equality Testing in $r$ rounds with failure probability $2^{-E}$ has communication volume $\Omega(Ek^{1/r})$. 2. There exists a protocol for solving Multiple Equality Testing in $r + \log^*(k/E)$ rounds with $O(k + rEk^{1/r})$ communication, thereby essentially matching our lower bound and that of Sa\u{g}lam and Tardos. Our original motivation for considering $p_{\mathrm{err}}$ as an independent parameter came from the problem of enumerating triangles in distributed ($\textsf{CONGEST}$) networks having maximum degree $\Delta$. We prove that this problem can be solved in $O(\Delta/\log n + \log\log \Delta)$ time with high probability $1-1/\operatorname{poly}(n)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages

[1]

Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion

A. Abboud, K. Censor - Hillel, S. Khoury, and C. Lenzen. Fooling views: A new lower bound technique for distributed computations under congestion. CoRR , abs/1711.01623, 2017

work page Pith review arXiv 2017
[2]

Brody, A

J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 106--113, 2014

work page 2014
[3]

Brody, A

J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Certifying equality with limited interaction. Algorithmica , 76(3):796--845, 2016

work page 2016
[4]

Barenboim and M

L. Barenboim and M. Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using N ash- W illiams decomposition. Distributed Computing , 22(5-6):363--379, 2010

work page 2010
[5]

Babai, P

L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory (preliminary version). In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 337--347, 1986

work page 1986
[6]

Buhrman, D

H. Buhrman, D. Garc \' a - Soriano, A. Matsliah, and R. de Wolf. The non-adaptive query complexity of testing k -parities. Chicago J. Theor. Comput. Sci. , 2013, 2013

work page 2013
[7]

Czumaj and C

A. Czumaj and C. Konrad. Detecting cliques in CONGEST networks. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC) , volume 121 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 16:1--16:15, 2018

work page 2018
[8]

Chiba and T

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing , 14(1):210--223, 1985

work page 1985

Show all 33 references

[9]

Chattopadhyay and T

A. Chattopadhyay and T. Pitassi. The story of set disjointness. SIGACT News , 41(3):59--85, 2010

2010
[10]

Y. - J. Chang, S. Pettie, and H. Zhang. Distributed triangle detection via expander decomposition. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , pages 821--840, 2019

2019
[11]

Y. - J. Chang and T. Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 66--73, 2019

2019
[12]

Drucker, F

A. Drucker, F. Kuhn, and R. Oshman. On the power of the congested clique model. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 367--376, 2014

2014
[13]

Dasgupta, R

A. Dasgupta, R. Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In Proceedings of the 15th International Workshop on Approximation, Randomization, and Combinatorial Optimization ( APPROX ) , pages 517--528, 2012

2012
[14]

D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press, 2009

2009
[15]

Fischer, T

O. Fischer, T. Gonen, F. Kuhn, and R. Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures ( SPAA ) , pages 153--162, 2018

2018
[16]

Feder, E

T. Feder, E. Kushilevitz, M. Naor, and N. Nisan. Amortized communication complexity. SIAM J. Comput. , 24(4):736--750, 1995

1995
[17]

M. L. Fredman, J. Koml \' o s, and E. Szemer \' e di. Storing a sparse table with O(1) worst case access time. J. ACM , 31(3):538--544, 1984

1984
[18]

Gonen and R

T. Gonen and R. Oshman. Lower bounds for subgraph detection in the CONGEST model. In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS) , volume 95 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 6:1--6:16, 2018

2018
[19]

The communication complexity of set intersection and multiple equality testing

Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang. The communication complexity of set intersection and multiple equality testing. In Proceedings 31st ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , pages 1715--1732, 2020

2020
[20]

H stad and A

J. H stad and A. Wigderson. The randomized communication complexity of set disjointness. Theory of Computing , 3(1):211--219, 2007

2007
[21]

Izumi and F

T. Izumi and F. Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 381--389, 2017

2017
[22]

Kushilevitz and N

E. Kushilevitz and N. Nisan. Communication Complexity . Cambridge University Press, 1997

1997
[23]

J. H. Korhonen and J. Rybicki. Deterministic subgraph detection in broadcast CONGEST . In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS) , volume 95 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 4:1--4:16, 2018

2018
[24]

Kalyanasundaram and G

B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. , 5(4):545--557, 1992

1992
[25]

L. Lovasz. Communication complexity: A survey. Technical Report TR-204-89, Computer Science Dept., Princeton University, 1989

1989
[26]

Amortized communication complexity of an equality predicate

Vladimir Nikishkin. Amortized communication complexity of an equality predicate. In Proceedings 8th International Computer Science Symposium in Russia ( CSR ) , volume 7913 of Lecture Notes in Computer Science , pages 212--223. Springer, 2013

2013
[27]

A. A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci. , 106(2):385--390, 1992

1992
[28]

Roughgarden

T. Roughgarden. Communication complexity (for algorithm designers). Foundations and Trends in Theoretical Computer Science , 11(3-4):217--404, 2016

2016
[29]

Rao and A

A. Rao and A. Yehudayoff. Communication complexity. (unpublished manuscript; available from the authors' homepages)
[30]

J. P. Schmidt and A. Siegel. The spatial complexity of oblivious k -probe hash functions. SIAM J. Comput. , 19(5):775--786, 1990

1990
[31]

Sa g lam and G

M. Sa g lam and G. Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 678--687, 2013

2013
[32]

A. C. - C. Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 222--227, 1977

1977
[33]

A. C. - C. Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 209--213, 1979

1979

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion

A. Abboud, K. Censor - Hillel, S. Khoury, and C. Lenzen. Fooling views: A new lower bound technique for distributed computations under congestion. CoRR , abs/1711.01623, 2017

work page Pith review arXiv 2017

[2] [2]

Brody, A

J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing ( PODC ) , pages 106--113, 2014

work page 2014

[3] [3]

Brody, A

J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Certifying equality with limited interaction. Algorithmica , 76(3):796--845, 2016

work page 2016

[4] [4]

Barenboim and M

L. Barenboim and M. Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using N ash- W illiams decomposition. Distributed Computing , 22(5-6):363--379, 2010

work page 2010

[5] [5]

Babai, P

L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory (preliminary version). In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 337--347, 1986

work page 1986

[6] [6]

Buhrman, D

H. Buhrman, D. Garc \' a - Soriano, A. Matsliah, and R. de Wolf. The non-adaptive query complexity of testing k -parities. Chicago J. Theor. Comput. Sci. , 2013, 2013

work page 2013

[7] [7]

Czumaj and C

A. Czumaj and C. Konrad. Detecting cliques in CONGEST networks. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC) , volume 121 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 16:1--16:15, 2018

work page 2018

[8] [8]

Chiba and T

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing , 14(1):210--223, 1985

work page 1985