Author

Jakub Tarnawski

h-index 4 View on Semantic Scholar

We have 2 of 11 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest

In this work we consider the Maximal Independent Set (MIS) problem and the metric Steiner Forest problem in the sublinear time setting, under the adjacency/distance matrix query model. First, we give an algorithm that estimates the size of an MIS up to a multiplicative factor of $(1+\eps)$ using $\tO(n^{4/3}/\eps^2)$ q...

S. Mahabadi, Jakub Tarnawski · 0 citations

Preprint Sep 2026

Hardness of Online Directed Steiner Network

This work gives an $\exp\!\bigl(\Omega(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs.

Gary Hoppenworth, Yao-Wei Long, S. Mahabadi et al. · 0 citations