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
  • Anti Ingel: Deep-Learning Guided Heuristic Search
  • Javier Gil Vidal: Quantum algorithms for topological data analysis
  • New! Rafieh Mosaheb: Quantum algorithms (starting in August)

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


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)

I'm the organizer of the NISQ Computing seminar at the CS institute.


My responsibilities in the Computer Science MSc curriculum

  • 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; fundamental quantum algorithms (QFT, QAA, QPE, Shor, ...).
  • 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.