---

Welcome! I'm a member of the Computer Science Institute of Charles University in Prague, Czechia. I like designing efficient algorithms and data structures for various problems, such as streaming quantile estimation, geometric streams, online scheduling, k-mer set analysis, etc.

Research group:

• Aleksander (Olek) Łukasiewicz – postdoc
• Tomáš Domes – PhD student, master thesis about quantile estimation defended in 2024
• Vojtěch Gaďurek – master student, working on set sketching data structures (IBLTs), bachelor thesis on IBLTs defended in 2024
• Jakub Komárek – master student, working on streaming quantile estimation with differential privacy
• Ján Plachý – master student, working on masked superstrings and compression of k-mer sets; presented his work on Pareto optimization at RECOMB-seq'26 and won the Czech-Slovak undergraduate student competition SVOČ 2025 in category TCS+ML
• several great bachelor students

Alumni:

• Ondřej Sladký – master student at ETH Zurich, working on data structures for k-mer sets, bachelor thesis Masked Superstrings for Efficient k-Mer Set Representation and Indexing, defended in 2024 and supervised together with Karel Břinda), won the Czech-Slovak undergraduate student competition SVOČ 2024 in category TCS+ML, and Dean's award for the best bachelor thesis in computer science in 2024 (article in Czech)
• Nicolaos (Nick) Matsakis – postdoc (2022-2024), now at TU Dresden
• and many great bachelor students

Short bio: From September 2018 to April 2021, I was happy to be a postdoc of Graham Cormode at the Department of Computer Science, University of Warwick. From 2014-2018, I was a PhD student at Charles University, fortunate to be advised by Jiří Sgall.

Full CV incl. publications (PDF)» TL;DR: Short CV (PDF)» (last update in November 2025)

Research interests: I am interested in theoretical computer science and combinatorics, with particular focus on designing efficient algorithms and data structures, specifically:

• streaming algorithms and data sketches/summaries (quantile estimation, geometric problems, adversarial robustness of sketches, etc.)
• online algorithms (primarily packing and scheduling problems, with particular focus on buffer management problems),
• approximation algorithms (e.g., approximately shortest superstrings and their applications in bioinformatics on representing k-mer sets of genomic data).

Teaching / Výuka

Regular seminars

• SToC every Tuesday at noon in S8!
• Algorithmic Problem Solving Seminar

LS 25/26 (summer semester 25/26):

🇨🇿 Teaching in Czech / výuka v češtině:

• Cvičení z Datových struktur I ve středu od 9:00 v S1
• Algoritmy a automaty pro učitele v pátek od 10:40 do 13:50 v učebně N9

Teaching in previous years / Výuka v předchozích letech

---

Selected or Recent Papers All Publications»

ORCID account   Google Scholar profile   arXiv search   dblp profile   Github  

• SplineSketch: Even More Accurate Quantiles with Error Guarantees
  with Aleksander Łukasiewicz and Jakub Tětek.
  In SIGMOD 2026. Preprint at arXiv.
• Masked superstrings as a unified framework for textual k-mer set representations
  with Ondřej Sladký and Karel Břinda.
  Preprint at bioRxiv. Presented at RECOMB-SEQ 2023 and Sequences 2024 by O. Sladký.
  Follow-up on indexing k-mer sets using masked superstrings and the masked Burrows-Wheeler Transform (MBWT).
• Streaming Facility Location in High Dimension via Geometric Hashing
  with Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Mingwei Yang.
  In FOCS 2022, p. 450-461, IEEE. doi:10.1109/FOCS54457.2022.00050. ArXiv preprint. Slides for FOCS.
  UPDATE (Feb'23): thanks to Arnold Filtser, our algorithmic framework gives a constant, that is O(1/ε), approximation in one pass, albeit with space increased to n^ε
• Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
  with Matthias Englert and Nicolaos Matsakis.
  In STOC 2022, p. 317-330, ACM. doi:10.1145/3519935.3520001. ArXiv preprint.
• Relative Error Streaming Quantiles
  with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.
  In PODS 2021 and Journal of the ACM. Best Paper (proof) Invited to JACM
  2022 ACM SIGMOD Research Highlight Award
  8-page summary in SIGMOD Record (2022). ArXiv preprint.
  Proof-of-concept Python code. Much better implementation in Java, C++, and Python in Apache DataSketches library. Video for PODS 2021. Video for WOLA 2020 (longer). WOLA slides.
• A Tight Lower Bound for Comparison-Based Quantile Summaries
  with Graham Cormode.
  In PODS 2020, p. 81-93, ACM, 2020, doi:10.1145/3375395.3387650. ArXiv preprint. BCTCS slides. Video record from PODS (starts at 29:00). View/hide summary.

  We prove a tight lower bound for the space used by a deterministic comparison-based quantile summary, which keeps track of all quantiles in a data stream (where items are linearly ordered), up to a small error. The lower bound matches the worst-case performance of the Greenwald-Khanna algorithm, up to a constant factor, and holds even for finding an approximate median in a data stream in the comparison-based model, where an algorithm only compares items and is otherwise completely oblivious of the universe of items.

• A φ-Competitive Algorithm for Scheduling Packets with Deadlines
  with Marek Chrobak, Łukasz Jeż, Jiří Sgall.
  In SODA 2019, p. 123-142, Society for Industrial and Applied Mathematics, 2019. doi:10.1137/1.9781611975482.9
  ArXiv preprint. Slides for DIMAP seminar (longer). SODA slides (shorter). View/hide summary.

  We designed a φ-competitive deterministic algorithm for bounded-delay packet scheduling. In this problem, packets arrive online into a buffer, each with a deadline, a weight, and of length 1. The goal is to schedule a packet in each time slot to maximize the total weight of scheduled packets. Our algorithm is based on the plan which is the maximum-weight subset of pending packets that can be scheduled starting from the current slot.

• Online Chromatic Number is PSPACE-Complete
  with Martin Böhm.
  In IWOCA 2016, LNCS 9843, p. 16-28, Springer, 2016.
  Best Student Paper ArXiv preprint. HALG 2017 poster. View/hide summary.

  We proved PSPACE-hardness of online coloring in which vertices of a known graph G arrives online and Painter colors them immediately without knowing to which induced subgraph of G the colored vertices correspond. Previously, PSPACE-hardness was known only in the variant in which some part of the graph is precolored (which makes the hardness proof substantially easier).

All Publications »