Collision Detection is Instance ptimal Under the Birthday Threshold

arXiv:2609.37342 · cs.DS, cs.CC, cs.CR · Submitted 2026-09-29 · Read on arXiv

cs.DS, cs.CC, cs.CR

Submitted: 2026-09-29

Updated: 2026-09-29

Terminology

• Query Complexity — 9× in this paper · explained in 2 episodes
• Embeddings — 6× in this paper · explained in 2 episodes
• Benchmark — 5× in this paper · explained in 2 episodes
• ACM SIGACT Symposium on Theory of Computing — 3× in this paper
• Aggregation — 2× in this paper · explained in 1 episode
• Symposium on Simplicity in Algorithms — 2× in this paper
• ACM-SIAM Symposium on Discrete Algorithms — 1× in this paper
• Adaptive Algorithm — 1× in this paper · explained in 1 episode
• Consistency — 1× in this paper · explained in 3 episodes
• Contextual Bandits — 1× in this paper · explained in 3 episodes
• Core — 1× in this paper · explained in 2 episodes
• Exchangeability — 1× in this paper · explained in 2 episodes
• Trace — 1× in this paper · explained in 2 episodes

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions