3 citations · 4 across the 6 of their papers we have counts for
14 papers
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 Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
Adam Karczmarz
We revisit the problem of finding optimal strategies for deterministic Markov Decision Processes (DMDPs), and a closely related problem of testing feasibility of systems of lin…
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…
Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems
Adam Karczmarz
We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically…
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
Adam Karczmarz, Jakub Pawlewicz, Piotr Sankowski
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension . Although the single-source and all-pairs variants of this problem are we…
Decomposable Submodular Function Minimization via Maximum Flow
Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee +2
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide impro…