Theory @ Tartu

Theoretical Computer Science

University of Tartu

Dirk Oliver Theis

Dirk Oliver Theis

Associate Professor of Theoretical Computer Science



Combinatorial and continuous optimization; quantum computing.

Recent Preprints

Randomness, Algorithms, Lower Bounds

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


  • Bivariate Partial Information Decomposition: The Optimization Perspective. With Abdullah Makkeh, Raul Vicente (Entropy, 2017)
  • BROJA-2PID: A Cone-Programming Based Estimator for Bivariate Partial Information Decomposition (Entropy, 2018)

Optimization praxis:

  • Analyzing Information Distribution in Complex Systems. With Sten Sootla, Raul Vicente. (Entropy, 2017)
  • Comparison of IP and CNF models for control of automated valet parking systems. With Abdullah Makkeh. Optimization Online 2017-02-5873 (ODS '17)

My Group (Algorithms & Theory)

Current PhD students

  • Abdullah Makkeh: Optimization applications [almost done]
  • Bahman Ghandchi (BSc Uni Tehran): Quantum circuits
  • NEW: Anti Ingel: Deep-Learning Guided Heuristic Search
  • NEW: Javier Gil Vidal: Quantum algorithms

Current MSc students

  • Tural İsmayilov: Deep learning for quantum computer programming

Former PhD students

  1. Mozhgan Pourmoradnasseri (BSc Sharif) ➡ postdoc in France

Selected Former BSc/MSc/Diploma students

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)


My responsibilities in the new Computer Science MSc curriculum (from fall 2018)

  • 05.008 Foundations of Math for CS
      • Fall, 1st graduate semester
      • ➢ Randomness, Hilbert spaces, quantum mechanics
  • 05.118 Quantum Computing
      • Spring, 2nd graduate semester
      • ➢ Quantum circuits, gates; fundamental quantum algorithms (QFT, QAA, QPE, Shor, ..., HHL).
  • 05.123 Advanced Quantum Algorithms (elective)
      • Fall, 3rd graduate semester
  • 05.124 Quantum Seminar
      • Every semester.

Current & Recent Courses

Spring 2018

  • MTAT.05.123 Quantum Machine Learning
  • MTAT.05.116 Algorithms & Theory Seminar

Fall 2017/18

  • MTAT.05.008 Discrete Mathematics
  • MTAT.05.116 Algorithms & Theory Seminar

Spring 2017

  • MTAT.05.120 Combinatorial + Convex Optimization
  • MTAT.05.118 Quantum Computing
  • MTAT.05.116 Algorithms & Theory Seminar

Fall 2016/17

  • MTAT.05.008 Discrete Mathematics w/ MTAT.05.124 Special Assignment in TCS
  • MTAT.05.121 TCS -- Communication Complexity
  • MTAT.05.116 Algorithms & Theory Seminar

Spring 2016: sabbatical



Theoretical Computer Science, University of Tartu, Ülikooli 17, 51014 Tartu, Estonia


  • dotheis /at/ ut /dot/ ee
  • dotheisatutdotee /at/ gmail /dot/ com

Spam policy.

  1. All emails containing "Call For Papers" and/or related keywords are filtered and automatically deleted.
  2. I block the sender address of every email containing invitations to publish in journals or conferences or participate in conferences (except if I know the sender).

Applications for Graduate Study.

Applications for graduate study (MSc+PhD, or PhD if you have a Master's) are welcome at any time, see also here. However, I currently take only students to specialize in quantum computing or quantum software technology.