Jakub Tětek

About me
Email: j (dot) "my surname without diacritics" (at) gmail.com

I am a co-founder and the CTO of Cognifence, an AI safety startup. Before that, I was a postdoc at INSAIT, Bulgaria. I did my PhD at Basic Algorithms Research Copenhagen (BARC), University of Copenhagen, where I was lucky to be supervised by Mikkel Thorup. My PhD thesis received the SCIENCE PhD Award 2025 from the university's Faculty of Science.

You can also find me on LinkedIn.

Selected Papers

See my Google Scholar profile for a complete list of my papers.

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
Richard Hladík, Jakub Tětek
FORC 2025, Best Student Paper

Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard Hladík, John Iacono, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
SODA 2025

Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
SOSA 2025

Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
Christian Janos Lebeda, Jakub Tětek
SOSA 2025

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, featured in Wired

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

Page updated

Google Sites

Report abuse

Jakub Tětek

About meEmail: j (dot) "my surname without diacritics" (at) gmail.com

Selected Papers

About me
Email: j (dot) "my surname without diacritics" (at) gmail.com