# Theory @ Tartu

### Theoretical Computer Science

### University of Tartu

# Graduate Studies

## I: First Year Master's — Fall Term

MTAT.03.286: Lecture course (6 ECTS)

### Design and Analysis of Algorithms

**Vitaly Skachek**

*Compulsory for all Computer Science master's students.*

- Minimum spanning tree, network flow algorithms, FFT, simplex algorithms for linear-programming problems, randomized algorithms, approximation algorithms (set cover, knapsack, TSP), rounding technique, primal-dual technique.

MTAT.05.008: Lecture course (6 ECTS)

### Mathematical Foundations of Computer Science

**Dirk Oliver Theis**

- Part I: Randomness — discrete probability, concentration of measure, applications (randomized algorithms, machine learning theory); Shannon entropy;
- Segue: Review of Linear Algebra — (finite) fields, vector spaces, bases, dimension, linear operators, matrices, Gaussian elimination master class;
- Part II: "Quantumness" — Hilbert space (Dirac notation, orthonormal bases, spectral theory of commuting operators, Fourier transform, tensor product, trace), postulates of quantum mechanics, entanglement (= Chapter 2 of Nielsen-Chuang); no-cloning theorem.

## II: First Year Master's — Spring Term

MTAT.07.002: Lecture course (6 ECTS)

### Cryptology I

**Dominique Unruh**

MTAT.07.024: Lecture course (6 ECTS)

### Quantum Cryptography

**Dominique Unruh**

MTAT.05.018: Lecture course (6 ECTS)

### Quantum Computing

**Dirk Oliver Theis**

- The circuit model, standard gates; knowing where we are: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE — but what about NP?
- Basic quantum algorithms: Deutsch-Jozsa, Grover, quantum Fourier transform, Simon, Schor (⟶factoring, discrete log), quantum phase estimation, ...
- More quantum algorithms: HHL, quantum machine learning, quantum persistent homology, ...

LTAT.04.002: Project (6 ECTS)

### Quantum Computer Programming

**Dirk Oliver Theis**

- QASM, Q#; other quantum programming languages.
- Quantum computer software architectures, compilers, embedded domain-specific languages; Microsoft Visual Studio Quantum Development Kit, QISKit.
- Specific challenges of near-term gate based devices (mapping, optimizing, ...)
- Group project.

## III: Second Year Master's — Fall Term

MTAT.05.082: Lecture Course (6 ECTS)

### Introduction to Coding Theory

**Vitaly Skachek**

- Communication model, error correction and detection, parameters of the codes, examples of codes, connections to secret sharing and wiretap channel model, Reed-Solomon codes and their decoding.

LTAT.04.xxx: Project (12 ECTS)

### Research Project in Theoretical Informatics

**All TCS faculty (Dominique Unruh, Helger Lipmaa, Vitaly Skachek, Dirk Oliver Theis)**

Intensive research project in preparation for the Master's thesis.

A selection of areas:

- Cryptography [Unruh, Lipmaa]
- Quantum crypto [Unruh]
- Quantum computing [Theis]
- Blockchain technology [Lipmaa, Skachek]
- Coding theory and information transmission [Skachek]
- Algorithms and lower bounds [Theis].

Student discuss possible topics directly with the supervisors.

## Every Term

MTAT.07.022: Seminar (3 ECTS, can be taken twice)

### Crypto seminar

**Dominique Unruh, Helger Lipmaa, Vitaly Skachek**

_TAT.xx.yyy: Seminar (3 ECTS, can be taken twice)

### Quantum seminar

**Dominique Unruh, Dirk Oliver Theis**

Each student reads a paper, gives a presentation about it.

## PhD-Level Courses

MTAT.05.121: Reading course (6 ECTS, can be taken 4 times)

### Methods in Theoretical Computer Science

**Dirk Oliver Theis**

- Advanced PhD-level reading courses on topics such as communication complexity, quantum complexity theory, quantum compiler construction, machine learning theory, advanced randomized algorithms, advanced data structures, ...

Students read, prepare, and present in detail the content of a paper or a book chapter.

MTAT.05.116: Seminar (3 ECTS, can be taken 4 times)

### Algorithms & Theory seminar

**Dirk Oliver Theis**