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é


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
  • Fooling Sets and the Spanning Tree Polytope
    w/ Kaveh Khoshkhah
    arXiv:1701.00350 (in: Inform Process Lett)
  • 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 -- Deep Learning Theory?

Former PhD students

  1. Mozhgan Pourmoradnasseri -- now postdoc in France

Selected BSc/MSc/Diploma students:

Current (MSc):
  • Liisi Kerik -- MSc project: quantum programming languages


Announcement: Spring 2018

  • MTAT.05.123 Quantum Machine Learning
    Requires quantum computing background. (Take 07.024 Quantum Crypto now!!)
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