62 citations · 316 across the 38 of their papers we have counts for
46 papers
Fully Dynamic Shortest Paths in Sparse Digraphs
Adam Karczmarz, Piotr Sankowski
We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with worst-ca…
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Adam Karczmarz, Piotr Sankowski
Algebraic techniques have had an important impact on graph algorithms so far. Porting them, e.g., the matrix inverse, into the dynamic regime improved best-known bounds for various…
Online matching with delays and stochastic arrival times
Mathieu Mari, Michał Pawłowski, Runtian Ren +1
This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this p…
Improving Ads-Profitability Using Traffic-Fingerprints
Adam Gabriel Dobrakowski, Andrzej Pacuk, Piotr Sankowski +2
This paper introduces the concept of traffic-fingerprints, i.e., normalized 24-dimensional vectors representing a distribution of daily traffic on a web page. Using k-means cluster…
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski
We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries ha…
Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski +1
Shapley values are one of the main tools used to explain predictions of tree ensemble models. The main alternative to Shapley values are Banzhaf values that have not been understoo…