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.

Example Study Plans

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