33 citations · 84 across the 22 of their papers we have counts for
32 papers
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Yinhao Dong, Pan Peng, Ali Vakilian +2
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algori…
A Configuration-LP Framework for Connected -Median Clustering
Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
We study the \emph{connected -median} clustering problem, a clustering problem that augments the classical -median objective with connectivity constraints. We focus on the \e…
Learning with Conflicts of Interest
Nischal Aryal, Arash Termehchy, Ali Vakilian +1
Financial, social, and political factors often prevent the interests of the owners of ML systems and services and their users from being perfectly aligned. ML systems often produce…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
Graph-Based Nearest-Neighbor Search without the Spread
Jeff Giliberti, Sariel Har-Peled, Jonas Sauer +1
Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set of points in , such that one can answer ap…
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…
Max-Cut with Multiple Cardinality Constraints
Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph , a partition of the vert…
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…
New and Improved Bounds for Markov Paging
Chirag Pabbaraju, Ali Vakilian
In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page fa…
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
Yinhao Dong, Pan Peng, Ali Vakilian
We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a -approximation for estimating the va…
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…
Improved Frequency Estimation Algorithms with and without Predictions
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen +2
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSket…
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…
Learning the Positions in CountSketch
Yi Li, Honghao Lin, Simin Liu +2
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g.,…
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
Eden Chlamtáč, Yury Makarychev, Ali Vakilian
We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves…
Faster Fundamental Graph Algorithms via Learned Predictions
Justin Y. Chen, Sandeep Silwal, Ali Vakilian +1
We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or si…