CS 6190: Lattice Algorithms

In July-Nov 2026, I will be teaching CS 6190: Lattice Algorithms.

Course Description

Lattices are beautiful mathematical objects, with a long and rich history, and many surprising applications ranging from cryptography to complexity theory. We will study the mathematical theory behind lattices, including basic definitions and properties, computational problems related to them and classic as well as current best known algorithms to solve these problems. If time permits, we will also look at hard problems related to random linear codes.

Administrative Information

Lectures are Wednesdays 2:00-3:15 pm and Thursdays, 3:30-4:45 pm in CSB 36. Office hours are by appointment: just send me an email and drop in! The TA for the course will be Anuja Modi (cs21d405@cse.iitm.ac.in).

Pre-requisites.

This course requires mathematical maturity, you should be comfortable with the language of proofs. Knowledge of algorithms, theory of computing (i.e. familiarity with reductions), some algebra and probability theory is required. The course will be self contained for the most part but you should be familiar with the tools and techniques used in theoretical computer science.

Requirements (Tentative).

• Class presentation (28 Oct - 5 Nov): 25%
• Midterm (Sep 30) :30%
• Final (Nov 11) :30%
• Class Participation: 15%

Resources

The course will primarily be based on the following courses:

• Oded Regev's course
• Divesh Aggarwal's course

Other useful related courses:

• Daniele Micciancio's course
• Chris Peikert's course

Topics

Below are the topics we have discussed in class

• Introduction to Lattices: Fundamental Parallelepiped; Equality of Lattices; Determinant of a Lattice; Shortest Non-Zero Vector and Towards Minkowski's First Theorem; Gram-Schmidt Orthogonalization; A Proof of the Formula of Determinant of a Lattice; Lower Bound on the Shortest Vector.
  Reference : Chapter 1 from Divesh Aggarwal's course.
  


• Lenstra Lenstra Lovász Algorithm: LLL as a Basis Finding Algorithm; LLL as Basis Reduction; Application of LLL: Cryptanalysis of Subset Sum based Cryptosystems.
  Reference : Chapter 2 from Divesh Aggarwal's course.
  
• Closest Vector Problem: Closest Vector Problem (CVP); CVP in 2^O(n2) or Babai's nearest plane algorithm; Closest Vector Problem using Voronoi Cell.
  Reference : Chapter 3 from Divesh Aggarwal's course and these notes from Oded Regev's course. For the Voronoi cell algorithm, we used these slides.
  


• Some Basic Complexity Results: CVP decision vs search, NP-hardness of exact CVP, SVP not harder than CVP.
  Reference : Lec 5 from Oded Regev's course.