Jakub Tětek
About me
Email: j (dot) "my surname without diacritics" (at) gmail.com
Email: j (dot) "my surname without diacritics" (at) gmail.com
I am a postdoc at INSAIT, Bulgaria in the group of Amir Abboud. Before that, I was lucky to be supervised by Mikkel Thorup at Basic Algorithms Research Copenhagen (BARC), University of Copenhagen. In the summer of 2023, I worked on differential privacy at Google Mountain View in the group of Badih Ghazi.
Research Interests
I am interested in differential privacy and randomized algorithms for large-scale computation. I am very interested in making contributions to theory that will find applications in practice.
I am in the job market for tenure-track positions, as well as research-oriented industry positions.
Selected Papers
See my Google Scholar profile for a complete list of my papers.
Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard Hladík, John Iacono, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
SODA 2025 (accepted)
Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
SOSA 2025 (accepted)
Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
Christian Janos Lebeda, Jakub Tětek
SOSA 2025 (accepted)
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Vaclav Rozhon, Jakub Tětek, Mikkel Thorup
FOCS 2024
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
FOCS 2024, Best Paper
Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
Christian Janos Lebeda, Jakub Tětek
PODS 2023, Distinguished Paper
Probgraph: High-performance and high-accuracy graph mining with probabilistic set representations
Maciej Besta, Cesare Miglioli, Paolo Sylos Labini, Jakub Tětek, Patrick Iff, Raghavendra Kanakagiri, Saleh Ashkboos, Kacper Janda, Michał Podstawski, Grzegorz Kwaśniewski, Niels Gleinig, Flavio Vella, Onur Mutlu, Torsten Hoefler
SC 2022, Best Paper
Estimating the Effective Support Size in Constant Query Complexity
Shyam Narayanan, Jakub Tětek
SOSA 2022
Sampling an Edge in Sublinear Time Exactly and Optimally
Talya Eden, Shyam Narayanan, Jakub Tětek
SOSA 2022
Massively Parallel Computation on Embedded Planar Graphs
Jacob Holm, Jakub Tětek
SODA 2022
A Nearly Tight Analysis of Greedy k-means++
Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhoň, Jakub Tětek
SODA 2022
Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
Jakub Tětek
ICALP 2022, Best Student Paper
Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses
Jakub Tětek, Mikkel Thorup
STOC 2022
Better Sum Estimation via Weighted Sampling
Lorenzo Beretta, Jakub Tětek
SODA 2022, Best Student Paper, Invited to HALG 2022
See also the slides and the recorded presentation
CountSketches, Feature Hashing and the Median of Three
Kasper Green Larsen, Rasmus Pagh, Jakub Tětek
ICML 2021
See also the slides, the poster, and the recorded presentation