Jakub Tětek

About me
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.

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