REVIEW 2 cited by
Communication Complexity of Collision
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each $x_i$ and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021).
Forward citations
Cited by 2 Pith papers
-
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Optimal unambiguous DNFs yield χ(G)≥exp(Ω(log² bp(G))), matching the known upper bound and resolving the Alon-Saks-Seymour problem up to constants.
-
Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
A matrix-discrepancy argument proves tight one-way quantum lower bounds for collision finding (Ω(N^{1/4})) and for streaming triangle finding (Ω(√Δ_V)) where Boolean-Hidden-Matching reductions fail.
Discussion (0). Continue with ORCID to comment.