---

Welcome! I'm a member of the Computer Science Institute of Charles University in Prague. 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.

Research interests

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

• streaming algorithms (e.g., for quantile estimation or geometric problems)
• online algorithms (currently mainly for buffer management problems, and more generally for packing and scheduling problems),
• approximation algorithms (e.g., shortest superstring, configuration linear programs),

and more.

I'm organizing Spring School 2022. I have served on the Program Committee of WAOA 2020.

CV (PDF)» Short CV (PDF)»

Teaching / Výuka

LS 21/22 (summer semester 21/22):

• A course on Algorithms for Data Streams, on Wednesday at 10:40 in S321 (corridor opposite to S3), starting from 23 February

Teaching in Czech / výuka v češtině v LS 21/22:

• 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 10:40 v N5

ZS 21/22 (winter semester 21/22, in Czech only):

• Matematické dovednosti v pondělí od 14:00 v N6
• Matematické dovednosti ve středu od 10:40 v N2
• Cvičení z Lineární algebry I v pondělí od 10:40 v N4
• Cvičení z Lineární algebry I v pátek od 9:00 v N7
• Cvičení z Lineární algebry I v pátek od 10:40 v N6

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  

• Streaming Facility Location in High Dimension via New Geometric Hashing
  with Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Mingwei Yang.
  ArXiv preprint.
• 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, 2022. doi:10.1145/3519935.3520001. ArXiv preprint.
• Streaming Algorithms for Geometric Steiner Forest
  with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.
  In ICALP 2022, p. 47:1--47:20. LIPIcs link. ArXiv preprint.
• Relative Error Streaming Quantiles
  with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.
  In PODS 2021, p. 96-108. doi:10.1145/3452021.3458323. 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 »