research
∙
11/14/2022
Massively Parallel Algorithms for b-Matching
This paper presents an O(loglogd̅) round massively parallel algorithm fo...
share
research
∙
03/02/2022
Near-Optimal Correlation Clustering with Privacy
Correlation clustering is a central problem in unsupervised learning, wi...
research
∙
06/15/2021
Correlation Clustering in Constant Many Parallel Rounds
Correlation clustering is a central topic in unsupervised learning, with...
research
∙
06/08/2021
Deterministic (1+ε)-Approximate Maximum Matching with 𝗉𝗈𝗅𝗒(1/ε) Passes in the Semi-Streaming Model
We present a deterministic (1+ε)-approximate maximum matching algorithm ...
research
∙
12/30/2020
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
Interval scheduling is a basic problem in the theory of algorithms and a...
research
∙
10/14/2020
Fairness in Streaming Submodular Maximization: Algorithms and Hardness
Submodular maximization has become established as the method of choice f...
research
∙
06/09/2020
Online Page Migration with ML Advice
We consider online algorithms for the page migration problem that use pr...
research
∙
06/08/2020
Fully Dynamic Algorithm for Constrained Submodular Optimization
The task of maximizing a monotone submodular function under a cardinalit...
research
∙
03/02/2020
Massively Parallel Algorithms for Distance Approximation and Spanners
Over the past decade, there has been increasing interest in distributed/...
research
∙
02/19/2020
Parallel Algorithms for Small Subgraph Counting
Subgraph counting is a fundamental problem in analyzing massive graphs, ...
research
∙
10/30/2019
Improved Local Computation Algorithm for Set Cover via Sparsification
We design a Local Computation Algorithm (LCA) for the set cover problem....
research
∙
07/12/2019
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Given a source of iid samples of edges of an input graph G with n vertic...
research
∙
07/11/2019
Walking Randomly, Massively, and Efficiently
We introduce an approach that enables for efficiently generating many in...
research
∙
05/07/2019
Adversarially Robust Submodular Maximization under Knapsack Constraints
We propose the first adversarially robust algorithm for monotone submodu...
research
∙
03/20/2019
Identifying Maximal Non-Redundant Integer Cone Generators
A non-redundant integer cone generator (NICG) of dimension d is a set S ...
research
∙
11/07/2018
Weighted Matchings via Unweighted Augmentations
We design a generic method for reducing the task of finding weighted mat...
research
∙
08/06/2018
Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams
Many tasks in machine learning and data mining, such as data diversifica...
research
∙
02/22/2018
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
We present O( n)-round algorithms in the Massively Parallel Computation ...
research
∙
12/21/2017
A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians
Sparsity-based methods are widely used in machine learning, statistics, ...
research
∙
11/07/2017
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
We study the classical problem of maximizing a monotone submodular funct...
research
∙
06/15/2017