Lattice reduction on an orthonormal lattice? Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you (quickly) figure out what that basis is?
Note that this may be much easier than finding the shortest vector in a general lattice, since (for instance) you know ahead of time exactly how long the shortest vector actually is.
Motivation: Suppose you wanted to use Brauer's induction theorem to compute the character table of a big group. After computing enough induced characters, you can check (by calculating a suitable determinant) that you have a set of representations generating the Grothendieck group. You know ahead of time that the irreducible representations form an orthonormal basis - so it's natural to ask whether you can use this information to quickly figure out what the characters actually are.
 A: I believe there is no known algorithm for the case of orthonormal lattices. I have seen this mentioned as an open question a couple of times. The only known algorithms are unfortunately those for general lattices, mainly LLL and its extension BKZ. 
The fact that the length of the shortest vector is known is not necessarily a strong indication that the problem is easy. A similar situation occurs with other families of lattices, especially so-called ideal lattices, which are lattices obtained through the canonical embedding of ideals in number fields (see, e.g.,  "Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors",  Peikert and Rosen, STOC 2007). And just like in the case of orthonormal lattices, the best known algorithms are the generic ones, despite the extra structure.
A: If there is an orthonormal basis, the lattice is $Z^n$ and one can
try to find all the $n$ norm 1 vectors up to sign. If $v_j$ is your
given basis and $w=\sum x_j v_j, x_j \in  Z$ is of norm one and
$v_i^*$ is the dual basis ($<v_i^*,v_j>=\delta_{ij}$), then
$|x_i|=|<v_i^*,w>| \le |v_i^*|$. If $G_{ij}=<v_i,v_j>$ is the Gram
matrix from the given
 basis, then $G^{-1}=<v_i^*,v_j^*>$ is the Gram for
the dual lattice. So one only need to search the finitely many $x
\in Z^n$  with $|x_j| \le \sqrt{(G^{-1})_{jj}}$ for all $j$ to solve
$x^TGx=1$. This gives a worst-case bound but it is still exponential
in $n$.
But I think one should just quickly find a few $w$ and reduce the
problem by looking in the orthogonal complement. If $w_1,...w_k$ are
norm 1 vectors found generating a sub-$Z^k$,then the  orthogonal
projection $v_j'$  of any $v_j$ on the orthogonal complement to the
space spanned by the $w's$ must be a lattice vector. We now pick
$v_j'$ only if the rank of the ortho-complement increased by one
until we find a generating set of $n-k$ $v_j'$ and we now have a
problem in lower dimension.
