11 papers
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 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…