BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Adam Karczmarz

Adam Karczmarz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsMachine Learning

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2022arXiv

Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary

We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries have been known for quite a long time, they do not, in general, allow reporting the underlying paths within the same time bounds, especially against an adaptive adversary. In this paper we develop the first known fully dynamic reachability data structures working against an adaptive adversary and supporting edge updates and path queries for two natural variants: (1) point-to-point path reporting, and (2) single-source reachability tree reporting. For point-to-point queries in DAGs, we achieve $O(n^{1.529})$ worst-case update and query bounds, whereas for tree reporting in DAGs, the worst-case bounds are $O(n^{1.765})$. More importantly, we show how to lift these algorithms to work on general graphs at the cost of increasing the bounds to $n^{1+5/6+o(1)}$ and making the update times amortized. On the way to accomplishing that, we obtain two interesting subresults. We give subquadratic fully dynamic algorithms for topological order (in a DAG), and strongly connected components. To the best of our knowledge, such algorithms have not been described before. Additionally, we provide deterministic incremental data structures for reachability and shortest paths that handle edge insertions and report the respective paths within subquadratic worst-case time bounds. For reachability and $(1+ε)$-approximate shortest paths in weighted digraphs, these bounds match the best known dynamic matrix inverse-based randomized bounds for fully dynamic reachability [v.d.Brand, Nanongkai and Saranurak, FOCS'19]. For exact shortest paths in unweighted graphs, the obtained bounds in the incremental setting polynomially improve upon the respective best known randomized update/distance query bounds in the fully dynamic setting.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Deterministic Parallel APSP Algorithm and its Applications

In this paper we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has $\tilde{O}(nm+(n/d)^3)$ work and $\tilde{O}(d)$ depth for any depth parameter $d\in [1,n]$. To the best of our knowledge, such a trade-off has only been previously described for the real-weighted single-source shortest paths problem using randomization [Bringmann et al., ICALP'17]. Moreover, our result improves upon the parallelism of the state-of-the-art randomized parallel algorithm for computing transitive closure, which has $\tilde{O}(nm+n^3/d^2)$ work and $\tilde{O}(d)$ depth [Ullman and Yannakakis, SIAM J. Comput. '91]. Our APSP algorithm turns out to be a powerful tool for designing efficient planar graph algorithms in both parallel and sequential regimes. One notable ingredient of our parallel APSP algorithm is a simple deterministic $\tilde{O}(nm)$-work $\tilde{O}(d)$-depth procedure for computing $\tilde{O}(n/d)$-size hitting sets of shortest $d$-hop paths between all pairs of vertices of a real-weighted digraph. Such hitting sets have also been called $d$-hub sets. Hub sets have previously proved especially useful in designing parallel or dynamic shortest paths algorithms and are typically obtained via random sampling. Our procedure implies, for example, an $\tilde{O}(nm)$-time deterministic algorithm for finding a shortest negative cycle of a real-weighted digraph. Such a near-optimal bound for this problem has been so far only achieved using a randomized algorithm [Orlin et al., Discret. Appl. Math. '18].

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Decomposable Submodular Function Minimization via Maximum Flow

This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on $O(1)$ elements of the ground set $V$ and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with $O(\vert V \vert)$ vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum $s,t$-cut problem in multiple settings.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Planar Reachability Under Single Vertex or Edge Failures

In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph $G$ can be preprocessed in $O(n\log^2{n}/\log\log{n})$ time, producing an $O(n\log{n})$-space data structure that can answer in $O(\log{n})$ time whether $u$ can reach $v$ in $G$ if the vertex $x$ (the edge~$f$) is removed from $G$, for any query vertices $u,v$ and failed vertex $x$ (failed edge $f$). To the best of our knowledge, this is the first data structure for planar directed graphs with nearly optimal preprocessing time that answers all-pairs queries under any kind of failures in polylogarithmic time. We also consider 2-reachability problems, where we are given a planar digraph $G$ and we wish to determine if there are two vertex-disjoint (edge-disjoint) paths from $u$ to $v$, for query vertices $u,v$. In this setting we provide a nearly optimal 2-reachability oracle, which is the existential variant of the reachability oracle under single failures, with the following bounds. We can construct in $O(n\log^{O(1)}{n})$ time an $O(n\log^{3+o(1)}{n})$-space data structure that can check in $O(\log^{2+o(1)}{n})$ time for any query vertices $u,v$ whether $v$ is 2-reachable from $u$, or otherwise find some separating vertex (edge) $x$ lying on all paths from $u$ to $v$ in $G$. To obtain our results, we follow the general recursive approach of Thorup for reachability in planar graphs [J.~ACM~'04] and we present new data structures which generalize dominator trees and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA~'17]. Our new data structures work also for general digraphs and may be of independent interest.

0 citations0 reviewsNo code linkedOpen access