Groupe d’études et de recherche en analyse des décisions

Lattice Reduction and Integer Least Squares Problems

Xiao-Wen Chang Université McGill, Canada

Integer least squares (ILS) problems, also referred to as closest vector problems, arise from several applications such as GPS, communications, and cryptanalysis etc. A general ILS problem is NP-hard. In this talk we consider two approaches: discrete search based branch and bound approach and continuous relaxation based branch and bound approach. The discrete search based approach involves two stages: lattice reduction and search. The often used lattice reduction strategy is the well-known LLL reduction. To make the search stage more efficient, in this talk we give an improved reduction strategy by using not only the lattice matrix but also the given target vector. For the continuous relaxation based approach, we show that using lattice reduction (preconditioning) as a preprocessing step can also make the computation much faster and propose some effective preconditioning strategies.