# Pavel Veselý

An approximation of my appearance (2018).

Quite an old approximation (2015).

Welcome! I'm an assistant professor at the Computer Science Institute of Charles University in Prague. The institute is a part of the Faculty of Mathematics and Physics (MFF).

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. In years 2014-2018, I was a PhD student at Charles University and my advisor was Jiří Sgall. I was also working a lot with his other PhD student Martin Böhm.

I have recently served on the Program Committee of WAOA 2020.

## News (from summer 2020)

- 2. 5. 2021: A new paper improving the competitive ratio upper bound for Longest Queue Drop (in shared memory switches) is accepted to ICALP 2021!
- 5. 3. 2021: The paper about relative error streaming quantiles is acepted to PODS 2021!

UPDATE (27. 5.): the paper will receive the**Best Paper Award**at PODS! - 18. 2. 2021: A new paper comparing t-digest and ReqSketch, which are two state-of-the-art quantile algorithms aiming at providing high accuracy for the tails. In particularm, it demonstrates that t-digest is prone to adversarial attacks and doesn't work for samples from a highly non-uniform distribution, even though it works very well on uniformly distributed data.

UPDATE (18. 5.): accepted to KDD 2021 (Applied Data Science Track)! - 26. 11. 2020: I've become a part of the team working on the Apache DataSketches project, where I'm in particular involved in implementing our algorithm for computing quantiles with relative error.
- 11. 11. 2020: A new paper about streaming algorithms for the geometric Steiner Forest problem. The interesting point is that it combines sketching and sampling techniques (previously used for MST) with the dynamic-programming approach previously used for an offline PTAS.
- 1. 9. 2020: I have started as an assistant professor at the Computer Science Institute of Charles University in Prague (currently, I'm on a leave there till April 2021).
- 17. 7. 2020: We have prepared a paper about relative error streaming quantiles with a new algorithm called ReqSketch for this problem. There's also a proof-of-concept Python implementation of our algorithm.

## Contact

- Email: <last name> (a strange sign) iuuk.mff.cuni.cz

## Teaching / Výuka

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

Teaching in previous years / Výuka v předchozích letech

## Research interests

I am interested in theoretical computer science and combinatorics, with particular focus on designing efficient algorithms and data structures, specifically:- streaming algorithms,
- online algorithms (currently mainly for buffer management problems),
- approximation algorithms,
- packing and scheduling problems,

## Projects

Selected work / projects (see also publications below):- Streaming algorithms:
- two papers about finding quantiles: a new algorithm with relative error and a tight lower bound for quantile summaries.
- geometric streaming algorithms: a new algorithm for Steiner Forest
- streaming algorithms for packing and scheduling problems

- Online algorithms, in particular for buffer management problems: new analysis for Longest Queue Drop

- Packet Scheduling, which is the topic of my PhD thesis; papers:
- FPT approximation, breaking both FPT and approximation lower bounds (paper Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices)
- Online Coloring (paper Online Chromatic Number is PSPACE-Complete)
- Colored Bin Packing (master thesis, paper)
- Waltz: a strong Tzaar-playing program (bachelor thesis and a paper)

## Publications

Papers are ordered basically from the newest to the oldest. See also my ORCID account, Google Scholar account, or dblp search.### Preprints

**Improved Analysis of Online Balanced Clustering**

with Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, and Jiří Sgall.

ArXiv preprint.**Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms**

with Graham Cormode, Abhinav Mishra, and Joseph Ross.

To appear in*KDD 2021*(Applied Data Science Track). ArXiv preprint.**Streaming Algorithms for Geometric Steiner Forest**

with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.

ArXiv preprint.