33 citations · 84 across the 22 of their papers we have counts for
8 papers · 1 filter
On Socially Fair Low-Rank Approximation and Column Subset Selection
Zhao Song, Ali Vakilian, David P. Woodruff +1
Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we stu…
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\…
Minimax Group Fairness in Strategic Classification
Emily Diana, Saeed Sharifi-Malvajerdi, Ali Vakilian
In strategic classification, agents manipulate their features, at a cost, to receive a positive classification outcome from the learner's classifier. The goal of the learner in suc…
A Polynomial-Time Approximation for Pairwise Fair -Median Clustering
Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad +3
In this work, we study pairwise fair clustering with groups, where for every cluster and every group , the number of points in from group mus…
Learning-Based Algorithms for Graph Searching Problems
Adela Frances DePavia, Erasmo Tani, Ali Vakilian
We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex has to traverse a (…
Scalable Algorithms for Individual Preference Stable Clustering
Ron Mosenzon, Ali Vakilian
In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is…
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…
Bayesian Strategic Classification
Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl +2
In strategic classification, agents modify their features, at a cost, to ideally obtain a positive classification from the learner's classifier. The typical response of the learner…