---

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.

Research group:

• Nicolaos (Nick) Matsakis – postdoc
• Ondřej Sladký – bachelor student (supervised together with Karel Břinda), thesis Masked Superstrings for Efficient k-Mer Set Representation and Indexing (submitted), already won the Czech-Slovak undergraduate student competition SVOČ 2024 in category Theoretical Computer Science!
• Tomáš Domes – master student (supervised together with Jakub Tětek), thesis about quantile estimation in preparation (expected PhD student since October 2024)
• bachelor students Vojtěch Gaďurek, Jan Adámek, Matúš Mitro, Adam Beneš, and Daniel Skýpala

Alumni: bachelor students 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 (e.g., for quantile estimation or 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., shortest superstring and its applications in bioinformatics on representing genomic data).

Teaching / Výuka

Come to our research seminar SToC!

LS 23/24 (summer semester 23/24):

• Streaming Algorithms for Big Data, scheduled on Mondays at 14:00 in S326 (inside corridor opposite to S3). The first lecture will take place on February 26.

Teaching in Czech / výuka v češtině v LS 23/24:

• Přednáška z Algoritmů a datových struktur 1 ve čtvrtek od 14:00 v N1
• Cvičení z Algoritmů a datových struktur 1 ve čtvrtek od 15:40 v N5

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

• Cvičení z Datových struktur I v pondělí od 9:00 v S7 (aneb ranní ptáče dál doskáče)
• Cvičení z Datových struktur I v pondělí od 10:40 v S8 povede hlavně Petr Chmel (a bude spravovat jeho stránky)
• Cvičení z Algoritmů a datových struktur II v pátek od 12:20 v S7

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 by O. Sladký.
• 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 »