Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10808
curl -X POST /api/v1/records/arxiv/2609.10808/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10808/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'