1 citations · 1 across the 6 of their papers we have counts for
10 papers
Pareto Inefficiency of EFX
Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX)…
Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest
Sepideh Mahabadi, Jakub Tarnawski
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 mo…
Hardness of Online Directed Steiner Network
Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi +1
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands , and asked to find a cheap subgraph connecting each terminal pair. In i…
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
Submodular maximization subject to matroid constraints is a central problem with many applications in machine learning. As algorithms are increasingly used in decision-making over…
Sublinear Metric Steiner Forest via Maximal Independent Set
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set of points in a metric space where distances are provided by means of que…
A 0.51-Approximation of Maximum Matching in Sublinear Time
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bou…
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of points in a metric space given to us by means of query access to an $n\…
Integrated Hardware Architecture and Device Placement Search
Irene Wang, Jakub Tarnawski, Amar Phanishayee +1
Distributed execution of deep learning training involves a dynamic interplay between hardware accelerator architecture and device placement strategy. This is the first work to expl…
Efficiently Computing Similarities to Private Datasets
Arturs Backurs, Zinan Lin, Sepideh Mahabadi +2
Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We abstract out th…
DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving
Foteini Strati, Sara Mcallister, Amar Phanishayee +2
Distributed LLM serving is costly and often underutilizes hardware accelerators due to three key challenges: bubbles in pipeline-parallel deployments caused by the bimodal latency…