33 citations · 81 across the 24 of their papers we have counts for
38 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)…
Random Fourier Features in Near-Linear Time
Sepideh Mahabadi, Sandeep Silwal, Tal Wagner
Random Fourier features approximate a shift-invariant kernel in , such as the Gaussian kernel , using independent samples from its spectra…
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…
Local Search for Fair Max-Min Diversification
Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar
Given points in a metric space, Max-Min diversification asks for a subset of points maximizing the minimum pairwise distance between the selected points. This is arguably t…
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…
Online Steiner Forest with Recourse
Yaowei Long, Sepideh Mahabadi, Sherry Sarkar +1
In the online Steiner forest problem we are given a graph , and a sequence of terminal pairs which arrive in an online fashion. We are asked to maintain a low-cost s…
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…
The Expiration Streaming Model: Diameter, -Center, Counting, Sampling, and Friends
Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi +5
An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where eac…
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…
Guessing Efficiently for Constrained Subspace Approximation
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu +2
In this paper we study constrained subspace approximation problem. Given a set of points in , the goal of the {\em subspace approximation} pr…
Streaming Algorithms for Network Design
Chandra Chekuri, Rhea Jain, Sepideh Mahabadi +1
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph and an integer…
Graph-Based Algorithms for Diverse Similarity Search
Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy +4
Nearest neighbor search is a fundamental data structure problem with many applications in machine learning, computer vision, recommendation systems and other fields. Although the m…
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\…
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…
Streaming Algorithms for Connectivity Augmentation
Ce Jin, Michael Kapralov, Sepideh Mahabadi +1
We study the -connectivity augmentation problem (-CAP) in the single-pass streaming model. Given a -edge connected graph that is stored in memory, and a stre…
Core-sets for Fair and Diverse Data Summarization
Sepideh Mahabadi, Stojan Trajanovski
We study core-set construction algorithms for the task of Diversity Maximization under fairness/partition constraint. Given a set of points in a metric space partitioned into $…
Tight Bounds for Volumetric Spanners and Applications
Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian
Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate…
Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
Given a set of vectors in , the goal of the \emph{determinant maximization} problem is to pick vectors with the maximum volume. Determinant maximization is th…
Improved Diversity Maximization Algorithms for Matching and Pseudoforest
Sepideh Mahabadi, Shyam Narayanan
In this work we consider the diversity maximization problem, where given a data set of elements, and a parameter , the goal is to pick a subset of of size maximi…
Approximation Algorithms for Fair Range Clustering
Sèdjro S. Hotegni, Sepideh Mahabadi, Ali Vakilian
This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick centers with the minimum clustering…
Composable Coresets for Constrained Determinant Maximization and Beyond
Sepideh Mahabadi, Thuy-Duong Vuong
We study algorithms for construction of composable coresets for the task of Determinant Maximization under partition constraint. Given a point set that is p…
Adaptive Sketches for Robust Regression with Importance Sampling
Sepideh Mahabadi, David P. Woodruff, Samson Zhou
We introduce data structures for solving robust regression through stochastic gradient descent (SGD) by sampling gradients with probability proportional to their norm, i.e., import…
Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?
Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi +2
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points and a radius parameter , the -near nei…