Question

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving techniques. A proper definition of the problem is found in the image below. enter image description here (The problem definition is borrowed from Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing by Laarhoven and Weger 2015. Here is the IACR page for the paper. )

(Refer to Sieving for shortest vectors in lattices using angular locality-sensitive hashing by Laarhoven 2015. The link is in the comments.)

I was curious if there is a way to have a similar spherical setting for the approximate NN problem for the finite field $\mathbb{Z}_2^n$. Particularly, I was wondering if there was a sphere definition relevant to $\mathbb{Z}_2^n$ that could be analogical or atleast very similar to the one in Definition 4. The one in definition 4 allows entire lattices to be embedded on the sphere i.e. $P$ is a lattice. The proposed distance measure could either be the $l_2$ norm or the hamming distance. It does not seem that it can be simply translated into finite fields.

I apologize if this is a naive question or does not make sense because I am a first time undergraduate researcher who is not very familiar with this forum and the level of questions asked here.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top