Swedish Summer School in Computer Science – S3CS 2018


About the Courses

Quantum Computing
(Ronald de Wolf)

Quantum computing tries to improve computers (making them faster, more secure etc.) by using quantum-mechanical effects like superposition, interference, and entanglement. There has been much progress in this area in the last 5 years, both in theory and in experimental realization. This course is meant as an introduction to the area for computer scientists and mathematicians. No prior knowledge of physics is assumed. In the 5 days of the course we'll cover the following topics:

  1. Introduction: some background, the quantum circuit model, early algorithms
  2. The quantum Fourier transform and Shor's algorithm for factoring integers (and breaking RSA)
  3. Grover's algorithm for search, quantum walk algorithms
  4. Complexity theory: query lower bounds, quantum complexity classes
  5. Quantum communication

Reading material: lecture notes.

Lattices and Cryptography
(Oded Regev)

Lattices have been investigated by mathematicians for over two centuries. In the last decade they have become an extremely active topic of research in computer science and cryptography. This is mainly due to Ajtai's seminal paper from 1996 ushering the beginning of lattice-based cryptography, as well as more recent work, such as the introduction of the LWE problem in 2005 and Gentry's construction of a fully homomorphic encryption scheme.

This course is mainly meant to serve as an introduction to the area, but will also include some recent developments. Specifically, we will attempt to cover:

  1. Introduction: history, Minkowski's theorem, basic definitions and results
  2. Algorithms for lattice problems (both efficient and exponential time), and applications (Coppersmith's method).
  3. The LWE problem and its quantum aspects. Public key cryptosystems, fully homomorphic encryption.
  4. Ring-LWE, ideal lattices and quantum algorithms

We will not assume any prior knowledge in the area. Reading material:

  1. Lecture notes
  2. Survey on crypto aspects
  3. Winter school on cryptography
Last modified: December 21, 2017