Optimal Boolean Locality-Sensitive Hashing

Abstract

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{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $\alpha$-corr.}}}[h(x) = h(y)])}{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $\beta$-corr.}}}[h(x) = h(y)])} \end{equation*} assigns nonzero probability only to members of the set of dictator functions $h(x)=\pm x_i$.