Pavel Veselý

An approximation of my appearance (2018).
An approximation of my appearance (2018).

A quite old approximation of my appearance (2015).
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.

My CV

News (from summer 2020)

Contact

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: and more.

Projects

Selected work / projects (see also publications below): Some older stuff:

Publications

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

Preprints

  1. Improved Analysis of Online Balanced Clustering
    with Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, and Jiří Sgall.
    ArXiv preprint.
  2. 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.
  3. Streaming Algorithms for Geometric Steiner Forest
    with Artur Czumaj, Shaofeng H.-C. Jiang, and Robert Krauthgamer.
    ArXiv preprint.

Conference papers

  1. Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
    with Antonios Antoniadis, Matthias Englert, and Nicolaos Matsakis.
    In ICALP 2021. LIPIcs link. ArXiv preprint. Video for ICALP (25 min).
  2. Relative Error Streaming Quantiles
    with Graham Cormode, Zohar Karnin, Edo Liberty, and Justin Thaler.
    In PODS 2021, p. 96-108 (Best Paper). doi:10.1145/3452021.3458323. 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.
  3. 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.
  4. Streaming Algorithms for Bin Packing and Vector Scheduling
    with Graham Cormode.
    In WAOA 2019, LNCS 11926, p. 72-88, Springer, 2020. ArXiv preprint. View/hide summary. WAOA slides.
  5. 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.
  6. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
    with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar.
    In STACS 2018, LIPIcs, p. 26:1--26:15, Schloss Dagstuhl, 2018. LIPIcs link. ArXiv preprint. View/hide summary.
  7. On Packet Scheduling with Adversarial Jamming and Speedup
    with Martin Böhm, Łukasz Jeż, Jiří Sgall.
    In WAOA 2017, LNCS 10787, p. 190-206, Springer, 2018. ArXiv preprint. WAOA slides. View/hide summary.
  8. Online Chromatic Number is PSPACE-Complete
    with Martin Böhm.
    In IWOCA 2016, LNCS 9843, p. 16-28, Springer, 2016.
    Best Student Paper of IWOCA 2016. ArXiv preprint. HALG 2017 poster. View/hide summary.
  9. Online Packet Scheduling with Bounded Delay and Lookahead
    with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.
    In ISAAC 2016, LIPIcs, p. 21:1--21:13, Schloss Dagstuhl, 2016. LIPIcs link, ArXiv preprint. MAPSP slides. View/hide summary.
  10. Online Algorithms for Multi-Level Aggregation.
    with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.
    In ESA 2016, Leibniz International Proceedings in Informatics (LIPIcs), p. 12:1-12:17, Schloss Dagstuhl, 2016. LIPIcs link, ArXiv preprint. View/hide summary.
  11. Better algorithms for online bin stretching
    with Martin Böhm, Jiří Sgall, Rob van Stee.
    In WAOA 2014, LNCS 8952, p. 236-247, Springer, 2015. ArXiv preprint. View/hide summary.
  12. Online colored bin packing
    with Martin Böhm, Jiří Sgall.
    In WAOA 2014, LNCS 8952, p. 35-46, Springer, 2015. ArXiv preprint. View/hide summary.
  13. WALTZ: a strong Tzaar-playing program
    with Tomáš Valla.
    In Computer Games, CCIS 408, p. 81–96, Springer, 2014. View/hide summary.

Journal papers

  1. Packet Scheduling: Plans, Monotonicity, and the Golden Ratio
    ACM SIGACT News, vol. 52(2), p. 72–84, 2021.
    DOI: 10.1145/3471469.3471481 Preprint.
    A column summarizing the ideas behind the φ-competitive algorithm for packet scheduling (SODA '19).
  2. Streaming Algorithms for Bin Packing and Vector Scheduling
    with Graham Cormode.
    Theory of Computing Systems, 2020.
    DOI: 10.1007/s00224-020-10011-y ArXiv preprint. View/hide summary.
  3. New Results on Multi-Level Aggregation
    with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.
    Theoretical Computer Science, vol. 861, p. 133-143, 2021.
    DOI: 10.1016/j.tcs.2021.02.016 View/hide summary.
  4. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.
    with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar.
    SIAM J. Discrete Math., vol. 35(1), p. 546–574, 2021.
    doi:10.1137/18M1209489. ArXiv preprint. View/hide summary.
  5. On Packet Scheduling with Adversarial Jamming and Speedup
    with Martin Böhm, Łukasz Jeż, Jiří Sgall.
    Annals of Operations Research, vol. 298, p. 7–42, 2021.
    doi:10.1007/s10479-019-03153-x. ArXiv preprint. WAOA slides. View/hide summary.
  6. Online Packet Scheduling with Bounded Delay and Lookahead
    with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.
    Theoretical Computer Science, vol. 776, p. 95-113, 2019.
    doi:10.1016/j.tcs.2019.01.013. ArXiv preprint. MAPSP slides. View/hide summary.
  7. Online Chromatic Number is PSPACE-Complete
    with Martin Böhm.
    Theory of Computing Systems, vol. 62(6), p. 1366–1391, Springer, 2018.
    doi:10.1007/s00224-017-9797-2. ArXiv preprint. HALG 2017 poster View/hide summary.
  8. Logarithmic price of buffer downscaling on line metrics
    with Marcin Bienkowski, Martin Bohm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jiří Sgall, Aleksandra Spyra.
    Theoretical Computer Science, vol. 707, p. 89-93, Elsevier, 2018, doi:10.1016/j.tcs.2017.10.008. ArXiv preprint. View/hide summary.
  9. Online Algorithms for Multi-Level Aggregation
    with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.
    Operations Research, vol. 68(1), p. 214-232, 2020.
    doi:10.1287/opre.2019.1847. ArXiv preprint. View/hide summary. .
  10. A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5
    with Martin Böhm, Jiří Sgall, Rob van Stee.
    Journal of Combinatorial Optimization, vol. 34(3), p. 810-828, Springer, 2017.
    doi:10.1007/s10878-017-0114-4. ArXiv preprint. View/hide summary.
  11. Online Bin Stretching with Three Bins
    with Martin Böhm, Jiří Sgall, Rob van Stee.
    Journal of Scheduling, vol. 20(6), p. 601-621, Springer, 2017, doi:10.1007/s10951-016-0504-y. ArXiv preprint. View/hide summary.
  12. Colored Bin Packing: Online Algorithms and Lower Bounds
    with Martin Böhm, György Dósa, Leah Epstein, Jiří Sgall.
    Algorithmica, vol. 80(1), p. 155-184, Springer, 2018.
    doi:10.1007/s00453-016-0248-2. View/hide summary.

Recommended books, articles, videos, etc.

Mosly about personal development, but generally about life, the Universe, and everything:



Last updated: July 2021