Speaker：Dr. Jinming Wen (CNRS,
Laboratoire LIP (U. Lyon, CNRS, ENSL, INRIA, UCBL),
France)
Time：Nov. 12, 14:30-15:30, 2015
Room：X2511
Abstract：
Integer leastsquares (ILS)
problems, also referred to as closest vector problems, havearisen from many
applications such as GPS, wireless communications,cryptanalysis, bioinformatics
etc. A general ILS problem is NP-hard. In this talk, we review some theory and
algorithms for ILS. We first introduce two theoretical results we recently
obtained, which rigorously justify the use of the well-known Lenstra, Lenstra
and Lovasz (LLL) reduction as preprocessing for solving ordinary ILS problem. We
then introduce some lower bound techniques to reduce the cost of solving the
ILS. Finally, we introduce some other types of ILS and some future research
problems.
