JT
Jakub Tarnawski
cs.DScs.LGcs.DCstat.MLcs.CRcs.CYcs.DMmath.COcs.ARcs.CC
On Valency
published · living versionsW_4fjg98t4·v1 · currentpublished
Semi-Streaming Reachability and Shortest Paths in Passes
with Gary Hoppenworth, George Z. Li, Sepideh Mahabadi
1 version
Preprints & journals
31 papers in the corpus · 2015–2026Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest2610.06053v1 · Sepideh Mahabadi, Jakub Tarnawski2026 · 0 citationsarXiv
Hardness of Online Directed Steiner Network2609.22605v1 · Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi et al.2026 · 0 citationsarXiv
Weighted Equitability and Matroid-Constrained Discrepancy2608.13983v1 · Krist'of B'erczi, Siyue Liu, Victor Reis et al.2026 · 0 citationsarXiv
Online Steiner Forest with Recourse2605.09821v1 · Yaowei Long, Sepideh Mahabadi, Sherry Sarkar et al.2026 · 0 citationsarXiv
Improved Algorithms for Fair Matroid Submodular Maximization2601.09860v1 · Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski2026 · 0 citationsarXiv
Sublinear Metric Steiner Forest via Maximal Independent Set2510.11627v1 · Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski et al.2025 · 0 citationsarXiv
A 0.51-Approximation of Maximum Matching in Sublinear Time2506.01669v1 · Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski2025 · 0 citationsarXiv
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover2411.09059v1 · Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski et al.2024 · 0 citationsarXiv
Integrated Hardware Architecture and Device Placement Search2407.13143v1 · Irene Wang, Jakub Tarnawski, Amar Phanishayee et al.2024 · 0 citationsarXiv
Efficiently Computing Similarities to Private Datasets2403.08917v1 · Arturs Backurs, Zinan Lin, Sepideh Mahabadi et al.2024 · 1 citationarXiv
DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving2403.01876v1 · Foteini Strati, Sara Mcallister, Amar Phanishayee et al.2024 · 2 citationsarXiv
Fairness in Submodular Maximization over a Matroid Constraint2312.14299v1 · Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard et al.2023 · 2 citationsarXiv
Fairness in Streaming Submodular Maximization over a Matroid Constraint2305.15118v3 · Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard et al.2023 · 1 citationarXiv
Near-Optimal Correlation Clustering with Privacy2203.01440v1 · Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi et al.2022 · 4 citationsarXiv
Harmony: Overcoming the Hurdles of GPU Memory Capacity to Train Massive DNN Models on Commodity Servers2202.01306v2 · Youjie Li, Amar Phanishayee, Derek Murray et al.2022 · 24 citationsarXiv
Online Edge Coloring via Tree Recurrences and Correlation Decay2111.00721v1 · Janardhan Kulkarni, Yang P. Liu, Ashwin Sah et al.2021 · 7 citationsarXiv
Correlation Clustering in Constant Many Parallel Rounds2106.08448v1 · Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovi'c et al.2021 · 7 citationsarXiv
On the Hardness of Scheduling With Non-Uniform Communication Delays2105.00111v1 · Sami Davies, Janardhan Kulkarni, Thomas Rothvoss et al.2021 · 4 citationsarXiv
Fairness in Streaming Submodular Maximization: Algorithms and Hardness2010.07431v2 · Marwa El Halabi, Slobodan Mitrovi'c, Ashkan Norouzi-Fard et al.2020 · 24 citationsarXiv
Efficient Algorithms for Device Placement of DNN Graph Operators2006.16423v2 · Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur et al.2020 · 32 citationsarXiv
Fully Dynamic Algorithm for Constrained Submodular Optimization2006.04704v2 · Silvio Lattanzi, Slobodan Mitrovi'c, Ashkan Norouzi-Fard et al.2020 · 3 citationsNeurIPS 2020
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints2004.13891v1 · Janardhan Kulkarni, Shi Li, Jakub Tarnawski et al.2020 · 11 citationsProc. of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pages 2770-2789
Scheduling with Communication Delays via LP Hierarchies and Clustering2004.09682v1 · Sami Davies, Janardhan Kulkarni, Thomas Rothvoss et al.2020 · 11 citationsarXiv
Beyond -Approximation for Submodular Maximization on Massive Data Streams1808.01842v1 · Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovi'c et al.2018 · 40 citationsProc. of 35th International Conference on Machine Learning (ICML), 2018, pages 3829-3838
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach1711.02598v1 · Slobodan Mitrovi'c, Ilija Bogunovic, Ashkan Norouzi-Fard et al.2017 · 29 citationsProc. of 30th Advances in Neural Information Processing Systems (NIPS) 2017, pages 4558-4567
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem1708.04215v4 · Ola Svensson, Jakub Tarnawski, L'aszl'o A. V'egh2017 · 45 citationsarXiv
The Matching Problem in General Graphs is in Quasi-NC1704.01929v2 · Ola Svensson, Jakub Tarnawski2017 · 27 citationsProc. of 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017, pages 696-707
Active Learning and Proofreading for Delineation of Curvilinear Structures1612.08036v2 · Agata Mosinska, Jakub Tarnawski, Pascal Fua2016 · 12 citationsProc. of Medical Image Computing and Computer-Assisted Intervention (MICCAI) 2017, pages 165-173
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios1607.07631v2 · Christos Kalaitzis, Ola Svensson, Jakub Tarnawski2016 · 3 citationsProc. of 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, pages 2654-2669
Constant Factor Approximation for ATSP with Two Edge Weights1511.07038v2 · Ola Svensson, Jakub Tarnawski, L'aszl'o A. V'egh2015 · 1 citationProc. of Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, pages 226-237
Fast Generation of Random Spanning Trees and the Effective Resistance Metric1501.00267v1 · Aleksander Madry, Damian Straszak, Jakub Tarnawski2015 · 50 citationsProc. of 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015, pages 2019-2036
Career total: 41 works. 31 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.