research
∙
08/17/2023
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Algebraic techniques have had an important impact on graph algorithms so...
share
research
∙
10/13/2022
Online matching with delays and stochastic arrival times
This paper presents a new research direction for the Min-cost Perfect Ma...
research
∙
05/31/2022
Improving Ads-Profitability Using Traffic-Fingerprints
This paper introduces the concept of traffic-fingerprints, i.e., normali...
research
∙
03/31/2022
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
We study reachability and shortest paths problems in dynamic directed gr...
research
∙
08/09/2021
Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
Shapley values are one of the main tools used to explain predictions of ...
research
∙
03/17/2021
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
We consider the problem of computing shortest paths in weighted unit-dis...
research
∙
03/05/2021
Decomposable Submodular Function Minimization via Maximum Flow
This paper bridges discrete and continuous optimization approaches for d...
research
∙
01/07/2021
A Deterministic Parallel APSP Algorithm and its Applications
In this paper we show a deterministic parallel all-pairs shortest paths ...
research
∙
07/11/2019
Walking Randomly, Massively, and Efficiently
We introduce an approach that enables for efficiently generating many in...
research
∙
07/04/2019
Min-Cost Flow in Unit-Capacity Planar Graphs
In this paper we give an O((nm)^2/3 C) time algorithm for computing min-...
research
∙
07/10/2018
Online Facility Location with Deletions
In this paper we study three previously unstudied variants of the online...
research
∙
09/22/2017
Planar Perfect Matching is in NC
In this paper we show that the problem of computing perfect matchings in...
research
∙
08/21/2017
Approximate nearest neighbors search without false negatives for l_2 for c>√(n)
In this paper, we report progress on answering the open problem presente...
research
∙
12/03/2016