---

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, dynamic geometric streams, online scheduling, k-mer sets, etc. My research is currently mainly supported by ERC CZ project on the development of streaming algorithms.

Research group:

• Aleksander (Olek) Łukasiewicz – postdoc
• Tomáš Domes – PhD student, master thesis about quantile estimation defended in 2024
• Ondřej Sladký – master student at ETH Zurich, working on data structures for k-mer sets, bc. 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
• Vojtěch Gaďurek – master student, working on set sketching data structures (defended bachelor thesis on the topic in 2024)
• bachelor students Ján Plachý, Matúš Mitro, Adam Beneš, and Daniel Skýpala

Alumni:

• Nicolaos (Nick) Matsakis – postdoc (2022-2024), now at Reykjavik University
• Alumni: bachelor students Jan Adámek (defense 2024), Katya Milyutina (defense 2023) and Petra Kaštánková (defense 2016)

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.

CV (PDF)» TL;DR: Short CV (PDF)» (last update in March 2024)

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

Come to our research seminar SToC!

ZS 24/25 (winter semester 24/25, in Czech only):

• Cvičení z Datových struktur I ve středu od 9:00 v S6 (aneb ranní ptáče dál doskáče)
• Algoritmy a automaty pro učitele v pátek od 10:40 do 13:50 v učebně S10
• Cvičení z Algoritmů a datových struktur II ve čtvrtek od 9:00 v S1 povede hlavně Tomáš Domes (detaily v poštovní Sově).

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  

• 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) and another one on k-mer set operations using function-assigned masked superstrings.
• 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 »