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 : 25%
• Midterm :30%
• Final :30%
• Class Participation: 15%

Resources

The course will have several commonalities with the following courses:

• Oded Regev's course
• Divesh Aggarwal's course
• Daniele Micciancio's course
• Chris Peikert's course

Topics

Below are the topics we will discuss in class. We'll cover some subset or superset of these, depending on time.

• Introduction :definitions, Minkowski's theorems. Material taught in class was based on this, this (for GSO) and this.
• Basis reduction: LLL and BKZ
• Babai's nearest plane algorithm for CVP
• Coppersmith algorithm to attack on RSA
• Some basic complexity results : CVP decision vs search, NP-hardness of exact CVP, SVP not harder than CVP, GapCVP({\sqrt{n}}) in NP intersect coAM (Goldreich-Goldwasser)
• A simply exponential algorithm for SVP (Ajtai-Kumar-Sivakumar)
• Dual lattices
• Introduction to Fourier analysis
• Banaszczyk's transference theorems
• Worst-case to average-case reduction
• As time permits: more algorithms (Arora-Ge, enumeration algorithms, performance in practice).