Algorithms & Theory in Tartu

The Algorithms & Theory group is a sub-group of Theoretical Computer Science, at the University of Tartu, in Tartu, Estonia.
The group started to exist in early 2013 with two new associate professors in Theoretical Computer Science. Since then, several postdocs, PhD students, and Master students were added.

Research areas

A bird's eye view of some of the areas which we are interested in:
  • Combinatorics with applications in algorithms and optimization
  • Random structures
  • Probabilistic analysis of algorithms
  • Randomized algorithms
  • Lower bounds
  • Combinatorial & algorithmic questions in science and engineering, e.g., coding theory, cryptography, bioinformatics, machine learning, neuroscience, ...
  • Optimization algorithms
  • Combinatorial optimization; Linear, Integer, and Convex Programming modeling
  • Consulting on algorithmic and combinatorial questions for companies


  • New offices Ülikooli 17 In March, Theoretical Computer Science moved into the new offices in 17 Ülikooli Street, opposite the university main building. Algorithms & Theory is on the 2nd floor, the large A&T Group room is 209, then there are some smaller offices and discussion rooms.
    Posted Apr 2, 2016, 1:05 AM by Dirk Oliver Theis
  • PhD position in Computational (Combinatorial) Optimization The Computer Science Institute of the University of Tartu, Estonia, is looking to fill aPhD-Position in Computational Optimization.The work environment is multi-national.  The language of instruction and communication is English.The PhD project consists in developing a software for the solution of a certain type of constrained optimization problems, and to apply it to problems in neuro science and data mining (in Tartu).  Moreover, the candidate will apply discrete optimization in some other, short term projects.The position also entails the following duties:write down intermediate findings in papers for publication in conferences and/or journals;teach 2h per term week (32 term weeks per year) in courses on algorithms and optimization.The 4-year PhD ...
    Posted May 1, 2015, 7:02 AM by Dirk Oliver Theis
  • Postdoc position Probabilistic combinatorics / random structures We are looking to fill a Postdoc position in Probabilistic combinatorics and random structures.The work environment is multi-national; interaction among faculty and between faculty and students/staff is in English.Remuneration. Salary after tax: Eur 1600--1850 (depending on qualification and/or whether you teach).  (Health insurance (w/o dental) is free in Estonia.)Put this into context with the cost of living: the average after tax income in Estonia is Eur 840. (For comparison: Spain 1600; Italy 1900; France 2100.) Duration. Between 6 months and 2+ years. Negotiated with the applicant. Your qualifications.  - Be fluent in English!!!! - Hold a PhD in Math or Theoretical Computer Science;  - Have experience and publications in probabilistic combinatorics and/or random structures ...
    Posted Aug 30, 2015, 6:59 AM by Dirk Oliver Theis
  • Online application system for Master's is now open The online system for applying for the Master's program in CS has opened on Dec 15. The application deadline is April 16. Transcripts and Bachelor degree certificate must be submitted both in the original language and in English! If you receive your Bachelor degree certificate after April 15, submit & post the other documents by that day, and send your Bachelor degree certificate as soon as you get it. To apply you need to submit documents on DreamApply website. You'll also need to send copies of some documents by regular mail (post them before April 16). The copies have to be certified (see here). Read the information on this page and on the DreamApply site very carefully! Every ...
    Posted Aug 30, 2015, 7:02 AM by Dirk Oliver Theis
  • Teaching in Spring '15  - MTAT.05.116 Algorithms & Combinatorics Seminar, this term about directed graphs. - MTAT.05.117 Randomness, by Mozhgan. - MTAT.05.120 Combinatorial Optimization, by DOT. - MTAT.05.182 Introduction to Coding Theory, by Vitaly.
    Posted Jan 3, 2015, 2:46 AM by Dirk Oliver Theis
  • Graphs in data analytics Check out this video lecture about graphs by Jim Webber, a data science practitioner, which he gave at the QCon 2014 developer conference. Apart from being quite funny (the accent!!), the presentation shows how graph problems are at the heart of business software for predictive or real-time analysis of data--even though, for our standards at A&T, the algorithmic problems he discusses in detail are, like, yawn easy been there done that. Further reading: Webber's book, Graph Databases; Webber's blog. DOT
    Posted Aug 30, 2015, 6:49 AM by Dirk Oliver Theis
  • Finally: Web site online at ac.cs.ut.ee This web site finally is online at http://ac.cs.ut.ee.  Thanks, Maria Gaiduk!
    Posted Nov 7, 2014, 7:10 AM by Dirk Oliver Theis
Showing posts 1 - 7 of 12. View more »

Discrete Lunch

  • June 15: Maximal m-free digraphs
    Today, Janno Siim gave his seminar presentation on maximal m-free digraphs. He presented, for example, the proof for the fact every maximal m-free digraphs has an m-king.
    Posted Jun 15, 2015, 5:50 AM by Dirk Oliver Theis
  • June 8: Zero-nonzero patterns of low-degree polynomials
    On Monday, DOT will present a theorem of Ronyai, Babai, and Ganapathy which gives an upper bound to the number of zero / nonzero patterns of a sequence of n polynomials in m variables of degree at most d. The perhaps most interesting fact is that the bound does not depend on n---only on m, d, and the number of non-zeros in the pattern.
    We will then discuss an application, due to Leslie Hogben and coauthors, to random matrix theory: the minimum rank of a matrix with a prescribed, random, zero-nonzero pattern.
    Posted Jun 7, 2015, 4:01 AM by Dirk Oliver Theis
  • May 25: Probabilistic recurrences II
    This week, Abdullah continued the proofs of the Karp's tail bounds on probabilistic recurrence relations.
    Posted May 31, 2015, 9:48 PM by Dirk Oliver Theis
  • May 18: Probabilistic recurrences
    Today, Abdullah will talk about random recursive relations, and what can be said about expectation and upper tail based on very general assumptions. The main results go back to a paper of Karp from the 1990s.
    The motivation behind studying these relations lies in the analysis of randomized algorithms.
    Posted May 18, 2015, 3:20 AM by Dirk Oliver Theis
  • May 11: Randomness extractors
    In today's Discrete Lunch, we'll discuss randomness extractors. A randomness extractor is a function which maps the points of a probability space to bit strings in such a way that, for all k, all length k strings are produced with equal probability (i.e., either 0 or 2-k.) One is then interested in the average length of the strings produced by the extractor.

    We will first prove the easy upper bound on the average length of the strings produced by an extractor: the entropy of the probability space. After that, we'll look at a few constructions of randomness extractors.
    Posted May 11, 2015, 2:20 AM by Dirk Oliver Theis
Showing posts 1 - 5 of 34. View more »