Theory @ Tartu

Theoretical Computer Science

University of Tartu

Dirk Oliver Theis

Dirk Oliver Theis

Associate Professor of Theoretical Computer Science



Quantum computing. Also randomness, (classical) algorithms & lower bounds, optimization & applications.

Recent Preprints

Randomness, Algorithms, Lower Bounds

  • 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)
  • On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope. With Kaveh Khoshkhah. arXiv:1702.01424
  • 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)

Optimization praxis:

  • Analyzing Information Distribution in Complex Systems. With Sten Sootla, Raul Vicente. (Entropy)
  • 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

Former PhD students

  1. Mozhgan Pourmoradnasseripostdoc 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)


Course Announcement (Spring 2018)

MTAT.05.123 Quantum Machine Learning

  • Requires quantum CS background.

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

  • 05.008 Foundations of Math for CS
  • ➢ Randomness, 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

Current & Recent Courses

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. When I receive invitations to publish in crappy conferences/journals, I do the following: 1. Create a filter which automatically deletes emails containing the name of the publisher; 2. Block the sender; 3. Report email as spam.

Office hours