Jakub Tarnawski

According to our database, Jakub Tarnawski authored at least 28 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Online Edge Coloring via Tree Recurrences and Correlation Decay.

Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab S. Sawhney, Jakub Tarnawski

SIAM J. Comput., February, 2024

Efficiently Computing Similarities to Private Datasets.

Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, Jakub Tarnawski

CoRR, 2024

DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving.

Foteini Strati, Sara McAllister, Amar Phanishayee, Jakub Tarnawski, Ana Klimovic

CoRR, 2024

2023

Fairness in Submodular Maximization over a Matroid Constraint.

Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, Thuy-Duong Vuong

CoRR, 2023

Fairness in Streaming Submodular Maximization over a Matroid Constraint.

Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, Jakub Tarnawski

Proceedings of the International Conference on Machine Learning, 2023

2022

Harmony: Overcoming the hurdles of GPU memory capacity to train massive DNN models on commodity servers.

Youjie Li, Amar Phanishayee, Derek Murray, Jakub Tarnawski, Nam Sung Kim

Proc. VLDB Endow., 2022

On the Hardness of Scheduling With Non-Uniform Communication Delays.

Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Correlation Clustering with Privacy.

Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

New graph algorithms via polyhedral techniques.

Jakub Tarnawski

it Inf. Technol., 2021

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines.

Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Piper: Multidimensional Planner for DNN Parallelization.

Jakub Tarnawski, Deepak Narayanan, Amar Phanishayee

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Correlation Clustering in Constant Many Parallel Rounds.

Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem.

Ola Svensson, Jakub Tarnawski, László A. Végh

J. ACM, 2020

Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints.

Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Efficient Algorithms for Device Placement of DNN Graph Operators.

Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur, Divya Mahajan, Fanny Nina Paravecino

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Fully Dynamic Algorithm for Constrained Submodular Optimization.

Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakub Tarnawski, Morteza Zadimoghaddam

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Fairness in Streaming Submodular Maximization: Algorithms and Hardness.

Marwa El Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos, Jakub Tarnawski

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Scheduling with Communication Delays via LP Hierarchies and Clustering.

Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Neue Graphen-Algorithmen mittels polyedrischer Methoden.

Jakub Tarnawski

Proceedings of the Ausgezeichnete Informatikdissertationen 2019., 2019

New Graph Algorithms via Polyhedral Techniques.

Jakub Tarnawski

PhD thesis, 2019

2018

Constant factor approximation for ATSP with two edge weights.

Ola Svensson, Jakub Tarnawski, László A. Végh

Math. Program., 2018

Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams.

Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, Ola Svensson

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

The Matching Problem in General Graphs is in Quasi-NC.

Ola Svensson, Jakub Tarnawski

Electron. Colloquium Comput. Complex., 2017

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios.

Christos Kalaitzis, Ola Svensson, Jakub Tarnawski

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach.

Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, Volkan Cevher

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Active Learning and Proofreading for Delineation of Curvilinear Structures.

Agata Mosinska, Jakub Tarnawski, Pascal Fua

Proceedings of the Medical Image Computing and Computer Assisted Intervention - MICCAI 2017, 2017

2016

Constant Factor Approximation for ATSP with Two Edge Weights - (Extended Abstract).

Ola Svensson, Jakub Tarnawski, László A. Végh

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

2015

Fast Generation of Random Spanning Trees and the Effective Resistance Metric.

Aleksander Madry, Damian Straszak, Jakub Tarnawski

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015