Skip to main content Skip to navigation

Pavel Veselý

Welcome! I was a postdoc (officially called Research Fellow) of professor Graham Cormode. Since May 2021, I'm an assistant professor at the Computer Science Institute of Charles University in Prague.

In years 2014-2018, I was a PhD student at the Computer Science Institute of Charles University in Prague. My adviser was professor Jiří Sgall.
More about me can be found in CV.

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

Contact

Office: my bedroom for most of the time (previously 2.31, Computer Science building, University of Warwick)
Email: vesely at iuuk dot mff dot cuni dot cz (note that my Warwick email address will stop working soon).
Please do not contact me regarding supervision of research projects (and apologies for not always responding to such requests).

News

  • 18. 2. 2021: A new paper comparing t-digest and ReqSketch, in particular demonstrating 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.
  • 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.
  • 16. 1. 2020: We updated the arXiv version of our optimal lower bound for quantile summaries (or, more simply, for finding the median in a data stream). We've added more intuition on how it works, and also included a new (relatively simple) lower bound for a related problem of biased quantiles.
  • 1. 7. 2019: We updated the arXiv version of the packet scheduling paper with a φ-competitive algorithm. The analysis is rewritten in an equivalent way that is hopefully more intuitive, and some other parts of the paper are also revised. Stay tuned, another revision will follow in O(1) months!
  • 14. 5. 2019: Two new papers about streaming algorithms appeared at arXiv: one with a tight lower bound for quantile summaries and the other about bin packing and vector scheduling.
  • 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.

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,

and more.

Some recent collaborators

Publications