We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in ... more >>>

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)
= O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

We investigate the computational complexity of finding an element of
a permutation group~$H\subseteq S_n$ with a minimal distance to a
given~$\pi\in S_n$, for different metrics on~$S_n$. We assume
that~$H$ is given by a set of generators, such that the problem
cannot be solved in polynomial time ... more >>>