Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

This tutorial will introduce the fundamentals of lattices, and problems on lattices such as the shortest vector problem (SVP) and closest vector problem (CVP). We will discuss these problems from a computational complexity point of view. Basis reduction (BR) is one of the widely used methods to solve instances of SVP and CVP approximately. After motivating procedures for BR in two dimensions, we will discuss BR algorithms in general. We will also talk about the efficiencies of such algorithms in practice. BR is one of the key steps in Lenstra-type algorithms for solving integer optimization or integer programming (IP) problems in polynomial time when the dimension is fixed. But such algorithms have not been implemented so far. We will focus on BR-based approaches to IP that have sound mathematical foundations but have also proven effective in practice. We will discuss BR-based reformulations for general IP instances, and the effectiveness of standard branch-and-bound approaches for solving these instances. We will also discuss lattice-based approaches to specific class of problems such as number partitioning.