8 papers
Strongly Polynomial Parallel Maximum Flow Revisited
Adam Karczmarz, Paweł Pilarski
We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with vertices and arcs, we show that a randomized paralle…
VARSHAP: Addressing Global Dependency Problems in Explainable AI with Variance-Based Local Feature Attribution
Mateusz Gajewski, MikoÅaj Morzy, Adam Karczmarz +1
Existing feature attribution methods like SHAP often suffer from global dependence, failing to capture true local model behavior. This paper introduces VARSHAP, a novel model-agnos…
Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni +1
Given a directed graph , a transitive reduction of (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of that preserves the reachability rela…
Accurate estimation of feature importance faithfulness for tree models
Mateusz Gajewski, Adam Karczmarz, Mateusz Rapicki +1
In this paper, we consider a perturbation-based metric of predictive faithfulness of feature rankings (or attributions) that we call PGI squared. When applied to decision tree-base…
On Incremental Approximate Shortest Paths in Directed Graphs
Adam Górkiewicz, Adam Karczmarz
In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertion…
Towards Scalable and Practical Batch-Dynamic Connectivity
Quinten De Man, Laxman Dhulipala, Adam Karczmarz +3
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for t…