Optimal Boolean Locality-Sensitive Hashing

Tobias Christiani

For $0\le \beta <\alpha <1$ the distribution $\mathcal{H}$ over Boolean functions $h:\{-1,1{\}}^d\to \{-1,1\}$ that minimizes the expression \begin{equation*} ρ_{α, β} = \frac{\lo…