Norms for lattice problems

Often lattice problems deal with finding lattice vectors which satisfy certain length/distance requirements. One question we might ask is how length/distance are defined. A natural choice is to use Euclidean lengths and distances (i.e. work in the \(\ell_2\) norm). It turns out that the \(\ell_2\) norm is the easiest norm to solve the typical lattice problems in, for example. SVP, CVP. This is formalized by a reduction from Regev and Rosen. In other words, there is a reduction from lattice problems in the \(\ell_2\) norm to lattice problems in the \(\ell_p\) norm.

One question we might have beyond this is what norms, other than the \(\ell_p\) norms, we can reduce lattice problems in the \(\ell_2\) norm to.

Slides going over a reduction summarizing the reduction and possible future directions.