---

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.

CV (PDF)» TL;DR: Short CV (PDF)» (last update Nov 22)

Research group: I now have an excellent postdoc, Nicolaos (Nick) Matsakis.

I am looking for Ph.D. students now, feel free to reach me by email.

Scientific events: I am organizing Spring School 2023 (also organized the event in 2022). There will be Highlights of Algorithms 2023 in Prague!

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 (chiefly packing and scheduling problems, with particular focus on buffer management problems),
• approximation algorithms (e.g., shortest superstring, configuration linear programs).

Teaching / Výuka

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

• Algorithmic Data Privacy – a course about how to release statistics without violating anybody's privacy. Time and place to be decided via "úmluva" (scheduling system of KAM/IUUK) – please give your time preferences by Wednesday 8 February!
• Tutorials on Randomized Algorithms for the lecture of J. Sgall – time and place to be decided via "úmluva" (webpage in preparation)

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

• Přednáška z Kombinatoriky a grafů 2 – ve středu od 12:20 v S4 (stránky v přípravě)
• Cvičení z Kombinatoriky a grafů 2 – v pondělí od 14:00 v S7 (stránky v přípravě)

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

• Matematické dovednosti ve středu od 14:00 v N6
• Matematické dovednosti ve čtvrtek od 9:00 v N4
• Cvičení z Algoritmů a datových struktur II v čtvrtek od 15:40 v S7
• Cvičení z Datových struktur I v pátek od 12:20 v S1

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 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.
• 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 »