Reduction from OV to Bichromatic Hamming Close Pair

FROM: OV TO: Bichromatic Hamming Close Pair

Implications

assume: OVH
then: there is no algorithm to solve target in time $O({2}^{o(d)}n^{2-\epsilon})$ on a set of $n$ points in $\{0,{1}\}^{c\log n}$

Year

2015

Reference

Alman, J., & Williams, R. (2015, October). Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 136-150). IEEE.

https://ieeexplore.ieee.org/abstract/document/7354392