{"id":"c059d32c-3dbf-4108-8765-ea9b464dcdd7","arxiv_id":"1908.11825","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Any r-round protocol for equality testing with failure probability 2^{-E} needs Ω(E k^{1/r}) communication, and near-matching protocols are given.","lead":"This paper proves new tradeoffs among rounds, communication, and error probability for randomized set intersection and equality testing protocols. It also gives a faster distributed algorithm for enumerating triangles in bounded-degree networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the invariant and round-by-round error transfer hold under the intended sender/receiver-ordered reading.","rationale":"The reader's verdict is ACCEPT with high confidence, and the reader identified the Invariant 3.3 / Lemma 3.7 error-transfer step as the weakest assumption. My independent stress-test focused on exactly that step, plus the round-by-round role swap that can obscure it. I found the proof internally consistent: the distributions D(j) and \\hat D(j) are defined with respect to the sender and receiver of message j, so the recursive comparison is valid in that order, and the base of the recursion is the true uniform distribution. The constants, the entropy-filtering lemmas, and the reduction of the final decision to a single coordinate all check out. No missing case, circular step, or unsupported assumption emerged. The concrete test suggested is a bookkeeping verification of the role-swap-heavy recursion, which is worth running to make the proof easier to audit, but it is not a suspected failure. Thus the reader's verdict should remain unchanged.","tokens_in":38235,"tokens_out":65495,"duration_ms":580490,"concrete_test":"Re-derive the unrolled hybrid recursion for r=2 and r=3 with explicit Alice/Bob labels, verifying that Q_j (error after message j, in sender/receiver order) satisfies Q_{j-1} >= 2^{-\\gamma_j-3} Q_j via Pr[m_j in M_j] >= 1/4 and Lemma 3.7; then confirm that the final lower bound 1/(4t) * exp(-3r - sum_j \\gamma_j) in Lemma 3.8 is achieved with the stated constants and that no hidden dependence on party identity enters the error event.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern found. The central claim, Theorems 2 and 3, is supported by the proof as written. The most delicate part is the recursive error-transfer step: at each round, D(j) is the sender's conditional distribution and \\hat D(j) is the receiver's resampled distribution, so comparisons of 'D(j) and \\hat D(j)' are in sender/receiver order, not fixed Alice/Bob order. Under this reading, the recursion Q_{j-1} >= 2^{-\\gamma_j-3} Q_j is valid: Lemma 3.5 gives Pr[m_j in M_j] >= 1/4, and Lemma 3.7 gives a 2^{-\\gamma_j-1} factor for the non-resampled receiver distribution. The base Q_0 is the true uniform distribution, so the lower bound transfers to the original distributional error. I also checked the constants in Lemmas 3.1, 3.2, 3.4-3.8 and found no circularity or missing case: the entropy lower bounds, the filter construction with beta1,beta2 >= 1/2, and the final 1/(4t) error lower bound are consistent, and the parameter assumptions (r <= (log k)/6, E >= 100 k^{1-1/r}/c) keep the accumulated error terms below 2^{-E}.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nSoft 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.\n\nBottom 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.","headline":"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.","tokens_in":39018,"tokens_out":950,"would_cite":true,"duration_ms":11289,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["communication complexity","equality testing","set intersection","round complexity","error probability","lower bounds","CONGEST model","triangle enumeration"],"falsifier":"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$.","tokens_in":38073,"feed_emoji":"🔢","tokens_out":7852,"duration_ms":73358,"temperature":0.7,"pith_summary":"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.","feed_headline":"New lower bound ties rounds, bits, and error for equality testing","feed_subtitle":"The result tells algorithm designers which tradeoff they must accept.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the minimax principle that converts the distributional lower bound into a worst-case randomized lower bound.","marker":"[Yao77]"},{"why":"It establishes the prior round-communication tradeoff for sparse SetDisjointness and ExistsEqual that this paper complements and whose dimension-reduction step it adapts.","marker":"[ST13]"},{"why":"It proves the prior ExistsEqual and SetIntersection tradeoffs and introduces a randomized reduction whose failure probability motivates treating error as an independent parameter.","marker":"[BCK+16]"},{"why":"It supplies the $\\Omega(k)$ communication lower bound for SetIntersection that serves as a baseline in the assumptions of the lower-bound proof.","marker":"[KS92]"},{"why":"It supplies the distributional lower bound for SetDisjointness, another baseline for the unavoidable $\\Omega(k)$ term.","marker":"[Raz92]"},{"why":"It provides the coloring-based amortized protocol used to exchange inner-product test bits at a cost proportional to the number of false positives.","marker":"[FKNN95]"},{"why":"It provides the perfect-hashing scheme whose succinct encoding underpins the deterministic reduction from SetIntersection to EqualityTesting.","marker":"[FKS84]"},{"why":"It provides the succinct perfect-hash encoding that carries the $O(k+\\log\\log p_{\\mathrm{err}}^{-1})$ overhead in Theorem 1.","marker":"[SS90]"},{"why":"It gives the CONGEST lower bound for local triangle enumeration that the new $O(\\Delta/\\log n+\\log\\log\\Delta)$ algorithm meets.","marker":"[IG17]"}],"fun_headline_variants":["No universal optimal: rounds, bits, error tradeoff proven","Equality testing can't optimize rounds, bits, and error at once","New lower bound forces a choice among rounds, bits, error","Set intersection: no free lunch in rounds, bits, and error","Tradeoff proven: rounds vs bits vs error in equality testing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No universal optimal: rounds, bits, error tradeoff proven","Equality testing can't optimize rounds, bits, and error at once","New lower bound forces a choice among rounds, bits, error","Set intersection: no free lunch in rounds, bits, and error","Tradeoff proven: rounds vs bits vs error in equality testing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001081,"raw_usage":{"total_tokens":4639,"prompt_tokens":1182,"completion_tokens":3457,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":798,"completion_tokens_details":{"reasoning_tokens":3368}},"tokens_in":798,"tokens_out":3457,"duration_ms":21897,"temperature":1.0,"reasoning_tokens":3368,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:05:43.081433+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}