Hardness of approximating the shortest vector problem in lattices
Lattice problems in NP ? coNP
On the impossibility of dimension reduction in l1