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 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:
  • Randomized algorithms of all flavors
  • Lower bounds, communication complexity, query complexity
  • Analysis of random structures and probabilistic analysis of algorithms
  • Combinatorial and convex optimization; optimization algorithms
  • Polytopes and extension complexity


  • Summer Course: Large-Scale Networks Data in the form of huge graphs (or networks) has become an important area for algorithm design. Networks with famous algorithmic challenges include the Facebook friend-graph (decide whom to show which ad) or the internet (search).Between June 27 and July 7, we have invited Babak Farzad to teach a series of lectures on Large-Scale Networks. Covered topics include:- network analysis (small-world etc)- stochastic models of network formation (preferential attachment etc)- strategic models of network formation (based on games, Nash equilibria).Mark it in your calendar!
    Posted May 13, 2017, 5:48 AM by Dirk Oliver Theis
  • PhD positions It's that time of the year again: We are looking to fill 2 positions for PhD students in Algorithms & Theory. One of the two is a joint supervision with Raul Vicente from Neuro, and will be concerned with the theory of Machine Learning.The other position is open to negotiations :). If suggestions are needed: sublinear algorithms; communication complexity. More info from Dirk Oliver Theis.
    Posted May 12, 2017, 6:37 AM by Dirk Oliver Theis
  • Mozhgan's defense date Mozhgan's defense date has been set: It will be June 2.
    Posted May 12, 2017, 6:33 AM by Dirk Oliver Theis
  • 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
Showing posts 1 - 5 of 15. View more »

Lunch Talks

  • June 9: MISC lunch -- SND continued
    Bahman continued his presentation of the Survivable Network Design approximation algorithm. We got stuck on some issues about vertex solutions to the LP... :-\
    Posted Jun 10, 2017, 1:22 AM by Dirk Oliver Theis
  • June 8: A&T Seminar presentation
    A straggler talk in the Algorithms & Theory seminar: Janno talked about proximal and augmented Lagrangian algorithms for machine learning problems with loss and regularization terms in the objective function.
    Posted Jun 10, 2017, 1:20 AM by Dirk Oliver Theis
  • June 7: APX Lunch on Survivable Network Design
    Bahman started presenting, in all the dirty details, the iterated LP-rounding approximation algorithm for survivable network design.
    Posted Jun 10, 2017, 1:17 AM by Dirk Oliver Theis
  • June 6: Foundations of Machine Learning
    After the exam stress has subsided, we started our usual schedule again: Over the summer, Tuesdays will be dedicated to the theory behind Machine Learning.
    Posted Jun 10, 2017, 1:16 AM by Dirk Oliver Theis
  • Fri May 12: Discrepancy upper bound
    We worked through the proof that every hypergraph with sufficiently many edges has a 2-coloring with discrepancy at most sqrt( n log(m/n) ). Highlights of the proof included the use of entropy and Kleitman's theorem.
    Posted Jun 10, 2017, 1:16 AM by Dirk Oliver Theis
Showing posts 1 - 5 of 45. View more »