---

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 have served on the Program Committee of WAOA 2020.

CV (PDF)» Short CV (PDF)»

Teaching / Výuka (currently 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 Papers All Publications»

ORCID account   Google Scholar profile   arXiv search   dblp profile   Github  

• Streaming Algorithms for Geometric Steiner Forest
  with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.
  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 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 »