16 citations · 40 across the 7 of their papers we have counts for
11 papers
Constructive plaquette compilation for the parity architecture
Roeland ter Hoeven, Benjamin E. Niehoff, Sagar Sudhir Kale +1
Parity compilation is the challenge of laying out the required constraints for the parity mapping in a local way. We present the first constructive compilation algorithm for the pa…
Online Min-Max Paging
Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale +1
Motivated by fairness requirements in communication networks, we introduce a natural variant of the online paging problem, called \textit{min-max} paging, where the objective is to…
Robust Algorithms under Adversarial Injections
Paritosh Garg, Sagar Kale, Lars Rohwedder +1
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the wo…
Fully-Dynamic Coresets
Monika Henzinger, Sagar Kale
With input sizes becoming massive, coresets -- small yet representative summary of the input -- are relevant more than ever. A weighted set that is a subset of the input is a…
How to Solve Fair -Center in Massive Data Models
Ashish Chiplunkar, Sagar Kale, Sivaramakrishnan Natarajan Ramamoorthy
Fueled by massive data, important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topi…
Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath, Sagar Kale, Ola Svensson
We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independent…
Weighted Matchings via Unweighted Augmentations
Buddhima Gamlath, Sagar Kale, Slobodan Mitrović +1
We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide eff…
Small Space Stream Summary for Matroid Center
Sagar Kale
In the matroid center problem, which generalizes the -center problem, we need to pick a set of centers that is an independent set of a matroid with rank . We study this probl…
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
Sagar Kale, Sumedh Tirodkar
We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our m…
Submodular Maximization Meets Streaming: Matchings, Matroids, and More
Amit Chakrabarti, Sagar Kale
We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a m…
Maximizing a Nonnegative, Monotone, Submodular Function Constrained to Matchings
Sagar Kale
Submodular functions have many applications. Matchings have many applications. The bitext word alignment problem can be modeled as the problem of maximizing a nonnegative, monotone…