Abstract
Eisenbrand and Venzin recently showed that the fastest algorithm for (large) constant-factor-approximate SVP and CVP in the L_2 norm can be made to work for all L_p norms. Their techniques are simple and elegant---the kind of proof that's surprising at first and then obvious in hindsight.
In follow-up work with Aggarwal, Chen, Kumar, and Li, we use their techniques to produce generic reductions, showing that any algorithm for SVP or CVP in one L_p norm yields algorithms in different L_p norms with only a constant factor loss in the approximation factor and a 2^{eps n} factor loss in the running time. (The reduction moves from larger p to smaller p for SVP and in the opposite direction for CVP.)
In my eyes (and perhaps only my eyes) all of this yields two surprising conclusions:
1) Lattice problems in different L_p norms are far more closely related than I originally thought.
2) If we accept the complexity-theoretic assumptions behind the recent fine-grained lower bounds for CVP in L_p norms (with Aggarwal, Bennett, and Golovnev), then the time-approximation factor tradeoff for CVP in L_p norms must behave... strangely.