Pith. sign in

REVIEW 4 major objections 5 minor 50 references

Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation

T0 review · 4 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Parallel batch-dynamic orientation matches sequential work bounds while keeping polylog span.

desk verdict The amortized result looks like a real contribution, but the worst-case theorems rest on an offline per-update flip bound that the paper cites only in amortized form, so I would not trust them as stated. read the letter →

arxiv 2602.17811 v2 pith:X7SRPUKM submitted 2026-02-19 cs.DC cs.DS

Guy Blelloch , Andrew Brady , Laxman Dhulipala , Jeremy Fineman , Kishen Gowda , Chase Hutton This is my paper
classification cs.DCcs.DS MSC 68W1068R10
keywords lowout-degreeorientationbatch-dynamicalgorithmsparallelarboricityworkefficiencydynamicgraphskylinecountergame
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that low out-degree orientation—directing edges so that no vertex keeps too many outgoing edges—can be maintained in the parallel batch-dynamic setting at essentially the same per-edge cost as the best sequential algorithms, without giving up polylogarithmic parallel time. It presents an amortized algorithm that maintains a 7c-orientation, where c is a known bound on the graph's arboricity (the densest subgraph's edge-to-vertex ratio), processing an inserted batch of size b in O(b) expected work and a deleted batch in O(b log n) expected work, with O(log^2 n) span. It also presents two worst-case algorithms: one maintains an O(c log n)-orientation with O(b sqrt(log n)) expected work, and the other maintains an O(c+log n)-orientation with O(b log^2 n) expected work and O(log^5 n) span. This matters because these are the first work-efficient parallel batch-dynamic results for this problem, and the paper's reductions show the gains propagate to maximal matching and explicit coloring.

What carries the argument

The argument runs through three pieces. First, a single-round repair step: for the amortized algorithm, statically orient the subgraph induced by vertices with out-degree above a cutoff, so a batch is fixed in one parallel phase and the potential—the count of edges disagreeing with an offline orientation—decreases enough to charge the work. Second, skylines: a formal way to choose a set of flips from high-degree vertices with enough total potential release; a key lemma shows that repeated skyline thresholds stay close, which keeps the degree bound stable. Third, the batch counter game: an abstract game where weights on counters (vertex potentials) can move under threshold-cap moves, and its

What would settle it

Construct a play of the batch counter game with cap H and starting weight Y where the maximum counter weight exceeds C*(Y+H log n) for every constant C; because the counter-game bound is the engine behind all worst-case out-degree bounds, such a play would falsify the claimed orientation quality.

Watch

Extended reading notes

Core claim

The core claim is that the sequential work bounds of dynamic orientation can survive parallelization. The key is to avoid the long chains of dependent one-edge flips that arise in the classic amortized approach; instead, each batch is repaired by collecting the offending out-edges and running a static orientation on that local subgraph, which reduces the same bad-edge potential while adding only constant-factor overhead. For worst-case guarantees, the paper introduces 'skyline' flips—subsets of edges from high-out-degree vertices whose size grows with the vertex's degree—and a 'batch counter game' that bounds how much potential can accumulate when entire batches move at once. The main theore

Load-bearing premise

The worst-case results assume that, for the degree bound they choose, there is a way to reorient edges in hindsight making at most O(log n) flips per update; if that assumption fails, the predicted update times and degree bounds no longer hold.

Editorial extensions

If this is right

  • Batch insertions cost amortized O(b) expected work, so the per-edge cost of parallel batching vanishes; the flip count is O(1)-competitive with any maintenance strategy, so no constant-factor improvement exists in this model.
  • The O(c+log n)-orientation worst-case result means that for graphs with arboricity at least log n, the parallel algorithm's degree guarantee is within a constant factor of the best sequential result while processing batches in polylog span.
  • Replacing the orientation routine in the paper's reductions yields parallel batch-dynamic maximal matching with amortized O(b(c+log n)) work and explicit coloring with worst-case O(b(c+log n) log^2 n) work, both with polylog span.
  • If randomized semisort is replaced by deterministic sorting, every algorithm remains with the same polylog span and only one extra log factor in work, so the parallelism does not depend on randomness.
  • The amortized algorithm is optimal in the number of edge flips up to constant factors, meaning its work bound is not just an artifact of the analysis but a genuine wall for this model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct extension the paper leaves implicit: the skyline/counter-game framework likely applies to k-core decomposition and other degree-constrained dynamic subgraph problems, since the counter game controls maximum accumulation of weight regardless of where the weight originates.
  • Because the batch counter game ignores arboricity, incorporating density constraints into the game might close the remaining gap to a work-efficient worst-case O(c)-orientation, eliminating the added log n in the degree bound for ultra-sparse graphs.
  • The worst-case algorithms assume a known upper bound on arboricity; an adaptive version that estimates the current arboricity would be a natural next step, though the paper does not attempt it.
  • For practical large-batch regimes, the deterministic bag construction means the O(log n) sorting penalty can be paid up front; the distinction between O(b) and O(b log n) matters most when batches are extremely large.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies parallel batch-dynamic algorithms for maintaining low out-degree orientations of undirected graphs with bounded arboricity c. It gives three main contributions: an amortized algorithm (Algorithm 1) maintaining a 7c-orientation with O(b) amortized expected work per inserted batch and O(b log n) per deleted batch and polylogarithmic span, claimed to be the first work-efficient parallel batch-dynamic orientation algorithm; a worst-case two-stage algorithm (Algorithm 2) maintaining an O(c log n)-orientation with O(b sqrt(log n)) expected worst-case work; and a worst-case reinsertion algorithm (Algorithm 3) maintaining an O(c+log n)-orientation with O(b log^2 n) expected worst-case work and O(log^5 n) span. The analysis is built on a new skyline primitive and a batch counter game, extending the counter-game framework of Berglin and Brodal. The paper also contributes a deterministic constant-work-per-operation parallel bag data structure and a roughly sorted list.

Significance. If the results are correct, this is a significant advance: the amortized algorithm matches the sequential work of Brodal--Fagerberg while processing whole batches in parallel, and the worst-case algorithms substantially improve over the prior parallel bounds of Liu et al. and Ghaffari--Koo. The skyline and batch counter game are novel technical tools with potential for further use. The paper is also commendable for being explicit about parameter tradeoffs and for providing deterministic variants with only logarithmic overhead. The central claims, however, rest on a small number of load-bearing proof steps: the existence of offline strategies with per-update worst-case flip bounds, the correctness of the batch counter game bound, and the recursive accounting for the reinsertion algorithm. These points need to be repaired or clarified before the theorems can be considered established.

major comments (4)
  1. [Section 6 and Section 7.6] The worst-case bounds in Theorems 6.1 and 6.2 require, as stated at the start of Section 6, an offline δ-orientation strategy κ making at most σ flips per update in the worst case. This per-update cap is used in Lemma 13.7 and then in the potential-injection bound (7.2). However, the manuscript never states or proves such per-update worst-case bounds for the cited strategies. Lemma 4.2 uses [13, Lemma 3] only as a total bound O(t_ins + t_del log n), and [6, Theorem 2] is not even stated. If these cited results are amortized or total only, then a single batch could concentrate the allowed flips and inject more than |B|ηϵ of potential, invalidating (7.2) and the domination argument. The authors should either state the exact per-update worst-case theorems from [13] and [6] and verify the parameters, or derive them. This is load-bearing for Theorems 2.5, 2.6, 6.1, and 6.2.
  2. [Section 12, Lemma 12.3] Lemma 12.3 claims M_i - T_i ≤ H for every i in a valid game sequence with strictly increasing thresholds. The proof asserts that for i=1, M_1=Y and T_1 ≥ Y-H. This is not a consequence of the game rules: R3 bounds the state after the move, not the starting state. For example, with Y=100, H=10, the first move can legally use threshold T_1=1 and move all counters to weight 1, giving M_1 - T_1 = 99 > H. The proof of Theorem 2.3 relies on Lemma 12.3 (via Lemma 12.7), so the counter game bound is not established as written. The bound is likely recoverable by applying R3 to states after the first move, since for i≥2 we have M_i ≤ T_{i-1}+H ≤ T_i+H, but the current text needs correction.
  3. [Section 7.5, Lemma 7.15 and Section 7.1] In Lemma 7.15, item (2), the proof concludes Δ(r,q) ≤ -bηϵ from the η skyline flips, the static orientation of the final skyline, and the removal of the high subset F. But q is defined as the potential of the orientation produced at the end of the invocation, and Algorithm 3 then reinserts F recursively. By (7.2), that recursive reinsertion can inject as much as |F|ηϵ of potential, so the stated accounting does not imply the claimed decrease relative to the final q. The recursive call is later treated as a separate bounded call, so the intended fix is to define the bounded call to stop at the removal of F and treat the recursive calls as separate moves, clarifying that intermediate missing-edge orientations are allowed in Theorem 7.11. As written, the indexing in Section 7.1 conflates the parent's output with the recursive call's output, and the proof of Theorem 7.16 is incomplete.
  4. [Section 7.4, Lemma 7.13] In the proof of item (2), Lemma 13.6 is applied to the second skyline S2 without verifying that S2 has sufficient height. Lemma 13.6 explicitly requires a skyline of sufficient height; otherwise static orientation can increase potential. If T(S2) < 4δ while T(S1) ≥ 4δ, the call may still be trivial because the final maximum degree is at most T(S2)+c+3c < 8δ, but this case is not handled. The proof should either show T(S2) ≥ 4δ or add this possibility to the trivial case.
minor comments (5)
  1. [Section 7.6] Typo: 'Berlgin and Brodal' should be 'Berglin and Brodal'.
  2. [Section 5, Definition 5.2] The notation Z[0,c'] is nonstandard; please clarify that ρ_v is an integer in {0,1,...,c'}.
  3. [Section 9, Algorithm 4] Line 3 defines E' and line 4 overwrites it with semisort(E'); using separate variable names would clarify the loop invariant.
  4. [Section 12.2] The proof of Lemma 12.1 could be shortened, but more importantly the notation 'by T_1 we mean T_{s+1}' is confusing; please reindex explicitly.
  5. [Section 14.1] The comparison with Blelloch and Brady [9] says 'runs in O(1) expected amortized work per update, and O(log^3 n) span whp' but does not name the paper in the prose; a citation label would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs reduce to external offline-orientation bounds, not to the paper's own outputs.

full rationale

I walked the derivation chain for the amortized algorithm (Algorithm 1, Theorem 2.1/2.2), the worst-case algorithms (Algorithms 2 and 3, Theorems 6.1/6.2, 2.5/2.6), the potential function, the skyline machinery, and the batch counter game. The amortized result is a parallelized Brodal–Fagerberg argument: Lemma 4.2 bounds total statically-oriented edges by an offline strategy's reorientations, with [13, Lemma 3] used as an external theorem. The worst-case results are conditional on an explicit hypothesis: Section 6 sets "δ, σ, ε to be values satisfying the following conditions: (1) there exists an offline δ-orientation strategy κ of B making at most σ flips per update per batch in the worst case." The potential-injection bound (7.2) is then derived in Lemma 13.7 by accounting from that hypothesis, not by assuming the theorem's conclusion (the algorithm's own out-degree or work bound). The counter-game max-weight bound (Theorem 6.4 / 2.3) is proved independently in Section 12. The paper's self-citations (e.g., randomized semisort [28], prior work [37]) are used as external primitives or baselines, and none of the central claims reduces to them by construction. The one genuine dependency — that the cited offline strategies indeed provide the per-update worst-case δ and σ values used in Section 7.6 — is a correctness or assumption risk, not a circularity, since the paper does not fit those values to its own conclusions. No equation in the paper is equivalent to its inputs by definition, and no fitted quantity is renamed as a prediction.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The paper's central claims rely on known-arboricity input, external offline orientation strategies, and randomized semisort; the new analytical entities (skyline, batch counter game) are internally defined and proven. No empirical free parameters are fitted to data.

free parameters (3)
  • Amortized threshold constants (tau*, tau', tau) = 6c/5, 11c/5, 24c/5
    Chosen by hand in Theorem 2.1 to make the potential denominator positive and produce the 7c-orientation bound.
  • TwoStage tradeoff parameters (delta, sigma, epsilon, c', H) = O(c sqrt(log n)), sqrt(log n), 1/sqrt(log n), c, 5c
    Chosen in Section 7.6 to derive O(c log n)-orientation with O(b sqrt(log n)) work from Theorem 6.1.
  • Reinsertion tradeoff parameters (delta, sigma, epsilon, c', H) = O(c), O(log n), 1/log n, ceil(c/log n), ceil(5c/log n)
    Chosen in Section 7.6 to derive O(c+log n)-orientation with O(b log^2 n) work from Theorem 6.2.
assumptions (5)
  • domain assumption Maximum arboricity c over the update sequence is known in advance and fixed.
    Both algorithm families assume a fixed known upper bound c; adaptive arboricity is explicitly out of scope.
  • domain assumption There exists an offline delta-orientation strategy kappa with worst-case sigma flips per update.
    The potential framework in Sections 7 and 13 depends on this; concrete delta and sigma are borrowed from [6,13,29] without being reproved.
  • domain assumption Randomized semisort achieves O(n) expected work and O(log n) span whp.
    Used in all randomized bounds; deterministic versions replace semisort with merge sort at an O(log n) work penalty.
  • domain assumption Brodal-Fagerberg's offline strategy [13, Lemma 3] maintains a tau*-orientation with O(log n) reorientations per deletion and no reorientations on insertions.
    Needed for Theorem 2.1 amortized optimality and for Reinsertion's delta=O(c), sigma=O(log n) parameter choices.
  • domain assumption Barenboim-Elkin static orientation [5] produces a (2+epsilon)c-orientation with stated work and span.
    Used as the static-orientation primitive in all three algorithms.
invented entities (2)
  • Skyline
    purpose: A subset of out-edges from high-degree vertices selected to flip in parallel while releasing potential.
    Internal combinatorial object; correctness rests on Section 11 lemmas, with no falsifiable external handle.
  • Batch counter game
    purpose: An n-counter game with legal T-moves used to dominate vertex potentials and bound maximum out-degree.
    Analytic abstraction proven in Section 12; the paper itself notes it ignores arboricity density constraints, so it is a proof instrument rather than an independently testable model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation." pith.science (2026). https://pith.science/paper/X7SRPUKM

@misc{pith2026260217811,
  author       = {Pith},
  title        = {Pith review of: Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X7SRPUKM}},
  note         = {Machine review of arXiv:2602.17811}
}
abstract

A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper we present work-efficient parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph, both in the amortized and worst-case settings. All results herein achieve polylogarithmic span; the focus of this paper is on minimizing the work, which varies across results. Both of our algorithms also have deterministic bounds with an additional logarithmic factor in the work. In the amortized setting, we give a parallel batch-dynamic algorithm that maintains a $O(c)$-orientation in $O(\log n)$ work per update in expectation, where $c$ is a known upper bound on the arboricity over the update sequence. This result is the parallelization of the classic dynamic orientation algorithm of Brodal and Fagerberg [WADS '99], and, in this setting, is a logarithmic factor faster than Liu et al. [SPAA '22]. In the worst-case setting, we give an $O(c+\log n)$-orientation with worst-case expected work per update $O(\log n)$. This is work-efficient, matching the best known sequential dynamic work of Berglin and Brodal [Algorithmica '20], and implies the existence of an $O(c)$-orientation algorithm with $O(\log^2 n)$ worst-case expected work per update. Our algorithm significantly improves, in the setting where $c$ is a fixed upper bound on arboricity, upon the parallel algorithm of Ghaffari and Koo [SPAA '25], which maintains a $O(c)$-orientation with $O(\log^9 n)$ worst-case work per edge with high probability (whp).

Figures

Figures reproduced from arXiv: 2602.17811 by the authors.

Figure 1
Figure 1. Example graph with high span for Brodal-Fagerberg’s Algorithm. Let the cutoff for [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Example graph orientation and skyline. A skyline is a subset of edges coming from [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Example of counter movements. Here, T = 10 and H = 3. Note that the total amount taken from counters above T, which is 11, is less than the amount added to counters, which is 10. Note that all counters end up with weight under T + H = 13, and that no counter below T loses weight. do), but nontrivial in the parallel batch-dynamic setting, and surprisingly has never been rigorously designed. In Section 10, we prove it… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example of finding a skyline of size 10, [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: New and old vertices from strata perspec [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

50 extracted references · 2 linked inside Pith

  1. [13]

    Dynamic representations of sparse graphs

    Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In Algorithms and Data Structures, Berlin, Heidelberg, 1999

    1999

  2. [6]

    A simple greedy algorithm for dynamic graph orientation.Algorithmica, 82(2):245–259, February 2020

    Edvin Berglin and Gerth Stølting Brodal. A simple greedy algorithm for dynamic graph orientation.Algorithmica, 82(2):245–259, February 2020

    2020

  3. [1]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. Parallel batch- dynamic graph connectivity. InACM Symposium on Parallelism in Algorithms and Architec- tures (SPAA). ACM, 2019

    2019

  4. [2]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel batch-dynamic trees via change propagation. InEuropean Symposium on Algorithms (ESA), 2020. 36

    2020

  5. [3]

    Parallel minimum cuts ino(mlog 2 n) work and low depth

    Daniel Anderson and Guy E Blelloch. Parallel minimum cuts ino(mlog 2 n) work and low depth. InProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Archi- tectures, pages 71–82, 2021

    2021

  6. [4]

    N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors.Theory of Computing Systems (TOCS), 34(2), Apr 2001

    2001

  7. [5]

    Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

    Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. InACM Symposium on Principles of Distributed Computing (PODC), pages 25–34, 2008

    2008

  8. [7]

    Fully dynamic matching in bipartite graphs

    Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. InInternational Colloquium on Automata, Languages, and Programming, pages 167–179. Springer, 2015

    2015

Show all 50 references
  1. [8]

    Faster fully dynamic matchings with small approximation ratios

    Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692–711. SIAM, 2016

    2016

  2. [9]

    Blelloch and Andrew C

    Guy E. Blelloch and Andrew C. Brady. Parallel batch-dynamic maximal matching with con- stant work per update, 2025

    2025

  3. [10]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020

    2020

  4. [11]

    Blelloch, Jeremy T Fineman, and Julian Shun

    Guy E. Blelloch, Jeremy T Fineman, and Julian Shun. Greedy sequential maximal independent set and matching are parallel on average. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012

    2012

  5. [12]

    Blumofe and Charles E

    Robert D. Blumofe and Charles E. Leiserson. Space-efficient scheduling of multithreaded computations.SIAM J. on Computing, 27(1), 1998

    1998

  6. [14]

    An efficient functional implementation of fifo queues.Information Processing Letters, 14(5):205–206, 1982

    F.Warren Burton. An efficient functional implementation of fifo queues.Information Processing Letters, 14(5):205–206, 1982

    1982

  7. [15]

    Adaptive out-orientations with applications

    Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quan- rud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3062–3088. SIAM, 2024

    2024

  8. [16]

    Fully-dynamicα+ 2 arboricity decompo- sitions and implicit colouring

    Aleksander BG Christiansen and Eva Rotenberg. Fully-dynamicα+ 2 arboricity decompo- sitions and implicit colouring. InIntl. Colloq. on Automata, Languages and Programming (ICALP), pages 42–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022

    2022

  9. [17]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms (3rd edition). MIT Press, 2009. 37

    2009

  10. [18]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Julienne: A framework for parallel graph algorithms using work-efficient bucketing. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017

    2017

  11. [19]

    Blelloch, and Julian Shun

    Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Theoretically efficient parallel graph algorithms can be fast and scalable.ACM Transactions on Parallel Computing (TOPC), 8(1), 2021

    2021

  12. [20]

    Parallel batch-dynamic graphs: Algorithms and lower bounds

    Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. Parallel batch-dynamic graphs: Algorithms and lower bounds. InACM-SIAM Symposium on Discrete Algorithms (SODA), 2020

    2020

  13. [21]

    Tight analysis of parallel randomized greedy mis

    Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy mis. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018

    2018

  14. [22]

    Nearly work-efficient parallel dfs in undi- rected graphs

    Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu. Nearly work-efficient parallel dfs in undi- rected graphs. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 273–283, 2023

    2023

  15. [23]

    Parallel batch-dynamic coreness decomposition with worst- case guarantees

    Mohsen Ghaffari and Jaehyun Koo. Parallel batch-dynamic coreness decomposition with worst- case guarantees. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025

    2025

  16. [24]

    Parallel dynamic maximal matching

    Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024

    2024

  17. [25]

    Optimal parallel sorting with comparison errors

    Michael T Goodrich and Riko Jacob. Optimal parallel sorting with comparison errors. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 355–365, 2023

    2023

  18. [26]

    Michael T. Goodrich, Riko Jacob, and Nodari Sitchinava.Atomic Power in Forks: A Super- Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork- Join Model, pages 2141–2153

  19. [27]

    Analysis of work-stealing and parallel cache com- plexity

    Yan Gu, Zachary Napier, and Yihan Sun. Analysis of work-stealing and parallel cache com- plexity. InACM-SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pages 46–60. SIAM, 2022

    2022

  20. [28]

    A top-down parallel semisort

    Yan Gu, Julian Shun, Yihan Sun, and Guy E Blelloch. A top-down parallel semisort. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015

    2015

  21. [29]

    Orienting dynamic graphs, with applications to maximal matchings and adjacency queries

    Meng He, Ganggui Tang, and Norbert Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. InInternational Symposium on Algorithms and Computation, pages 128–140. Springer, 2014

    2014

  22. [30]

    Explicit and implicit dynamic col- oring of graphs with bounded arboricity.arXiv preprint arXiv:2002.10142, 2020

    Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic col- oring of graphs with bounded arboricity.arXiv preprint arXiv:2002.10142, 2020

    2002 arXiv

  23. [31]

    Real-time queue operations in pure lisp.Information Processing Letters, 13(2):50–54, 1981

    Robert Hood and Robert Melville. Real-time queue operations in pure lisp.Information Processing Letters, 13(2):50–54, 1981

    1981

  24. [32]

    JaJa.Introduction to Parallel Algorithms

    J. JaJa.Introduction to Parallel Algorithms. Addison-Wesley Professional, 1992. 38

    1992

  25. [33]

    Addison Wesley Longman Publishing Co., Inc., USA, 1992

    Joseph J´ aJ´ a.An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc., USA, 1992

    1992

  26. [34]

    Karp and Vijaya Ramachandran

    Richard M. Karp and Vijaya Ramachandran. Parallel algorithms for shared-memory machines. InHandbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). MIT Press, 1990

    1990

  27. [35]

    Orienting fully dynamic graphs with worst-case time bounds

    Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,Automata, Languages, and Programming, pages 532–543, Berlin, Heide...

    2014

  28. [36]

    Adjacency queries in dynamic sparse graphs.Information Processing Letters, 102(5):191–195, 2007

    Lukasz Kowalik. Adjacency queries in dynamic sparse graphs.Information Processing Letters, 102(5):191–195, 2007

    2007

  29. [37]

    Parallel batch- dynamic algorithms for k-core decomposition and related graph problems

    Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batch- dynamic algorithms for k-core decomposition and related graph problems. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 191–204, 2022

    2022

  30. [38]

    Eugene W. Myers. An applicative random-access stack.Information Processing Letters, 17(5):241–248, 1983

    1983

  31. [39]

    C. St.J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs.Journal of the London Mathematical Society, s1-36(1):445–450, 1961

    1961

  32. [40]

    Simple deterministic algorithms for fully dynamic maximal matching.ACM Transactions on Algorithms (TALG), 12(1):1–15, 2015

    Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching.ACM Transactions on Algorithms (TALG), 12(1):1–15, 2015

    2015

  33. [41]

    Cambridge University Press, 1999

    Chris Okasaki.Purely functional data structures. Cambridge University Press, 1999

    1999

  34. [42]

    Fully dynamic mis in uniformly sparse graphs.ACM Transactions on Algorithms (TALG), 16(2):1–19, 2020

    Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs.ACM Transactions on Algorithms (TALG), 16(2):1–19, 2020

    2020

  35. [43]

    Dynamic (1 +ϵ)-approximate matchings: A density-sensitive approach

    David Peleg and Shay Solomon. Dynamic (1 +ϵ)-approximate matchings: A density-sensitive approach. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712–729. SIAM, 2016

    2016

  36. [44]

    Near-optimal fully dynamic densest subgraph

    Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. InPro- ceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 181–193, New York, NY, USA, 2020. Association for Computing Machinery

    2020

  37. [45]

    A parallel batch-dynamic data structure for the closest pair problem.CoRR, 2020

    Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. A parallel batch-dynamic data structure for the closest pair problem.CoRR, 2020

    2020

  38. [46]

    Parallel batch-dynamic k-d trees.arXiv preprint arXiv:2112.06188, 2021

    Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic k-d trees.arXiv preprint arXiv:2112.06188, 2021

    2021 arXiv

  39. [47]

    Optimal batch-dynamic kd-trees for processing-in-memory with applications

    Yiwei Zhao, Hongbo Kang, Yan Gu, Guy E Blelloch, Laxman Dhulipala, Charles McGuf- fey, and Phillip B Gibbons. Optimal batch-dynamic kd-trees for processing-in-memory with applications. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025. 39 9 Appendix: ...

    2025

  40. [48]

    If 2(2 i −1) =x i, thenx i−1 will be zero, so this is true

  41. [49]

    If 2 i −1> x i, then 2 i −2≥x i, so it follows that 2(2 i−1 −1)≥x i =x i−1

  42. [50]

    replacement

    If 2 i −1≤x i and 2(2i −1)̸=x i, thenx i−1 =x i −2 i + 1. Since 2(2 i −1)̸=x i by assumption and 2(2i −1)≥x i by the inductive hypothesis, we havex i <2(2 i −1) and sox i ≤2(2 i −1)−1, sox i −2 i + 1≤2(2 i −1)−1−2 i + 1 = 2i −2 = 2(2 i−1 −1), as desired. Lemma 10.2.The functio...

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.