The LSH amplification exponent

ProofGraduate⏱ 1 hourRAGlshamplificationsublinearexponent

Theory: Vector Search — Exact and Approximate Nearest Neighbours →

Problem

Given an $(r,cr,p_1,p_2)$ -sensitive family, derive the AND/OR amplification with $k$ concatenated hashes and $L$ tables, show that $k = \log_{1/p_2}N$ and $L = N^\varrho$ with $\varrho = \log(1/p_1)/\log(1/p_2)$ give query time $\tilde O(N^\varrho)$ , and verify $\varrho<1$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Product quantisation budget arithmetic	RAG	Numerical	Beginner	30 min
Recall composes multiplicatively	RAG	Numerical	Beginner	15 min
The random-hyperplane collision probability	RAG	Proof	Intermediate	30 min
Implement SimHash LSH and measure recall run	RAG	Coding	Advanced	3 hours
Why space-partitioning trees fail in high dimension	RAG	Proof	Advanced	30 min