People‎ > ‎

Dirk Oliver Theis

Associate Professor

Diplom in math w/ minor CS Heidelberg (2002)
Dr. rer.nat. Heidelberg (2005, summa cum laude) under Gerhard Reinelt
Habilitation to Priv.-Doz. (math) Magdeburg (2012)

Complete resumé

The official homepage of Dirk Oliver Theis is now here.

This page will no longer be updated.


Randomness, Lower Bounds, Algorithms, Quantum Computing, Optimization; Applications of Optimization

Recent Talks

Projects and Activities

Bicliques--Combinatorics, Communication, and Optimization. Funded by ETAG (2015-2018)

Dagstuhl seminar #15082: Limitations of Convex Programming (report)

Dagstuhl seminar #13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (report)

Recent Preprints

Randomness, Algorithms, Lower Bounds:

  • Extended spanning star forest problems
    w/ Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jerome Monnot
    (in: COCOA '17)
  • The Rectangle Covering Number of Random Boolean Matrices
    w/ Mozhgan Pourmoradnasseri
    (in: Electron J Comb)
  • On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope
    w/ Kaveh Khoshkhah
  • The (minimum) rank of typical fooling set matrices
    w/ Mozhgan Pourmoradnasseri
  • On the Graph of the Pedigree Polytope
    w/ Abdullah Makkeh, Mozhgan Pourmoradnasseri
  • The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Ext.Abs.)
    w/ Abdullah Makkeh, Mozhgan Pourmoradnasseri
    arXiv:1611.08419 (in: CALDAM '17)
  • Nondeterministic Communication Complexity of Random Boolean Functions
    w/ Mozhgan Pourmoradnasseri
    arXiv:1611.08400 (in: TAMC '16)
  • Short note on the number of 1-ascents in dispersed Dyck paths
    w/ Kairi Kangro, Mozhgan Pourmoradnasseri


  • Bivariate Partial Information Decomposition: The Optimization Perspective
    w/ Abdullah Makkeh, Raul Vicente
    (in: Entropy)


  • Analyzing Information Distribution in Complex Systems
    w/ Sten Sootla, Raul Vicente
    (in: Entropy)


Current PhD students

  • Abdullah Makkeh -- Optimization & applications
  • Bahman Ghandchi -- Quantum Machine Learning
  • NEW: Javier Gil Vidal -- Quantum computing
  • NEW: Anti Ingel -- Understanding Deep Learning

Former PhD students

  1. Mozhgan Pourmoradnasseri ➡ postdoc in France

Selected BSc/MSc/Diploma students:


Announcement: Spring 2018

  • MTAT.05.123 Quantum Machine Learning
    Requires quantum background. (Take 07.024 Quantum Crypto now!!)

The University of Tartu is making adjustments to the Master's in Computer Science curriculum. The changes will take effect in Fall 2018. I will teach the following courses.

  • 05.008 Foundations of Math for CS
    ➢ Probability, Hilbert spaces, quantum mechanics
    Fall, 1st graduate semester
  • 05.118 Quantum Computing
    Spring, 2nd graduate semester
  • 04.002 Quantum Computer Programming
    ➢ Practical supplement to 05.118
    Spring, 2nd graduate semester
  • 05.124 Quantum Seminar
Fall 2017/18
  • MTAT.05.008 Discrete Mathematics
  • MTAT.05.121 Theory of Machine Learning
  • MTAT.05.116 Algorithms & Theory Seminar
Spring 2017
  • MTAT.05.018 Quantum Computing
  • MTAT.05.020 Convex & Combinatorial Optimization
  • MTAT.05.116 Algorithms & Theory Seminar
Fall 2015/16
  • MTAT.05.008 Discrete Mathematics with
    MTAT.05.124 Special Assignment in TCS
  • MTAT.05.121 TCS -- Communication Complexity
  • MTAT.05.116 Algorithms & Theory Seminar
Spring 2016:   sabbatical

Fall 2015/16
Spring 2015
Fall 2014/15
Spring 2014
Fall 2013/14
  • MTAT.05.008 Discrete Mathematics
  • MTAT.05.005 Enumerative Combinatorics
  • MTAT.05.116 Discrete Math Seminar
Spring 2013
  • MTAT.07.025 Mathematics for Cryptology