---

Interested in working with me? Please do no hesitate to contact me at .

PhD positions available within the framework of a computation social choice project, led by Martin Koutecký and me.

Below you can find particular suggestions for individual software project (SW; „ročníkový projekt“), bachelor (Bc.) or master (Mgr.) theses in areas of my interest. I'm also open to lead a project in a related area, such as in approximation algorithms.

Some of the topics below are suitable for doctoral (Ph.D.) research as well.

Streaming algorithms (for processing massive datasets in one pass with small memory); some examples of possible topics:

• Sampling and sparse recovery – SW, Bc.
• quantile estimation – SW, Bc., Mgr., Ph.D. An example of possible SW/Bc. project:
  • Attacks and robustness of quantile summaries. Recent work has compared a heuristic called t-digest and a relative-error streaming algorithm for estimating quantiles. While the former uses very little space, independent of the input size, but is not robust, the latter provides worst-case guarantees but its space usage grows with time. These two algorithms use very different techniques, and the question is whether we can get "best of both worlds". The project goal would be to evaluate approaches that combine both approaches.
• Geometric streaming algorithms – SW, Bc., Mgr., Ph.D. An example of SW/Bc. project:
  • Estimating the MST cost in the plane. There is a streaming algorithm estimating the cost of the minimum spanning tree in the plane using a small amount of memory. However, this algorithm is only analyzed mathematically, and it would be interesting to know how does it perform on real-world or synthetic datasets.
  • Clustering high-dimensional spaces. The goal would be to experimentally evaluate recent dynamic streaming algorithms for k-median and facility location problems. A part of the project may be to check whether the ideas from the latter paper may give a better space bound for k-median.
• packing or scheduling problems in streaming – SW, Bc., Mgr. (more theoretically inclined topics, although with a possibility to carry out some experiments for the SW project)
• algorithms for vote streams (as part of a GA ČR project on computational social choice with Martin Koutecký) – SW, Bc., Mgr.

Applications of string or stremaing algorithms in bioinformatics (SW, Bc., Mgr.)

• Intended for processing large genomic data

Online algorithms (in essence, they are about making decisions without any knowledge of the future; see also competitive analysis)

• computer-assisted search for hard instances, lower bounds, and algorithms – SW, Bc.
• packet scheduling or other buffer management problems – Bc., Mgr.