# Pavel Veselý

An approximation of my appearance (2018).

Quite an old approximation (2015).

Welcome! I'm currently a postdoc of Graham Cormode at Department of Computer Science, University of Warwick. Starting from May 2021, I will be an assistant professor at Computer Science Institute of Charles University in Prague.

In years 2014-2018, I was a PhD student at Computer Science Institute of Charles University in Prague. The institute is a part of Faculty of Mathematics and Physics (MFF). My advisor was Jiří Sgall and I was also working a lot with his other PhD student Martin Böhm.

## News (till 09/2018)

- 25. 9. 2018: I successfully defended my thesis, which ended up my studies (after 4 years of PhD, 9 years at Charles University, and 22 years in total!).
**3. 9. 2018: I have started as a postdoc of Graham Cormode at the University of Warwick.**- 17. 7. 2018: The thesis is finally submitted together with a new paper on bounded-delay packet scheduling containing a φ-competitive algorithm!

## Contact

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

## Teaching / Výuka

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

**Theory meets Practice: worst case behavior of quantile algorithms**

with Graham Cormode, Abhinav Mishra, and Joseph Ross.

ArXiv preprint.**Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop**

with Antonios Antoniadis, Matthias Englert, and Nicolaos Matsakis.

ArXiv preprint.**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.

To appear in*PODS 2021*. ArXiv preprint. Proof-of-concept Python code. WOLA 2020 talk video. WOLA slides.