CS 6190: Lattices in Computer Science.

In Semester 1, 2017-2018, Satya Lokam and I will be teaching CS 6190: Recent Trends in Theoretical Computer Science. The focus of our course will be Lattices in Computer Science.

Course Description

The theme of the course will be the utilization of lattices in computer science. 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 (whatever is relevant to Computer Science), including basic definitions and properties, computational problems related to them and classic as well as current best known algorithms to solve these problems.

Administrative Information

Lectures are Thursdays 2:00-3:15 pm and Fridays, 3:25-4:40 pm in CSB 36. Office hours are by appointment: just send Satya/me an email and drop 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%
• 3-4 Assignments : 20%. Assignments will be open ended in nature and collaboration is encouraged.
• Midterm :20%
• Final :20%
• Class Participation: 15%

Resources

The course will have several commonalities with the following courses:

• Oded Regev's course
• Daniele Micciancio's course
• Chris Peikert's course
• Vinod Vaikuntanathan's course
• See also Daniele's talk and Chris Peikert's expository talks.

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).

Assignments

To be announced.