pith. sign in

arxiv: 2604.27966 · v1 · submitted 2026-04-30 · 💻 cs.DS

Simpler and Improved Replacement Path Coverings

Davide Bil\`o , Shiri Chechik , Keerti Choudhary , Sarel Cohen , Martin Schirneck This is my paper

Pith reviewed 2026-05-07 04:53 UTC · model grok-4.3

classification 💻 cs.DS
keywords replacement path coveringderandomizationconditional expectationsfault-tolerant shortest pathsgraph coveringsalgorithm derandomizationsubgraph families
0
0 comments X

The pith

A simpler conditional-expectations derandomization achieves Õ(f L^{f+o(1)}) replacement path coverings with Õ(f^{5/2} L^{o(1)}) queries.

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

The paper presents a simpler deterministic construction for (L,f)-replacement path coverings that avoids algebraic machinery. By applying the method of conditional expectations to an existing randomized construction, it recovers a covering value of Õ(f L^{f+o(1)}) subgraphs while cutting the time to identify the right subfamily for any fault set F down to Õ(f^{5/2} L^{o(1)}). The authors also supply a new randomized construction whose size is Õ((L/f)^f L^{o(1)}) and prove this size is tight up to the L^{o(1)} factor when f = o(log L). These coverings let data structures preserve short replacement paths after removing at most f edges.

Core claim

An (L,f)-replacement path covering is a family of subgraphs such that for every set F of at most f edges there exists a subfamily that avoids F and still contains a shortest s-t path of length at most L whenever one exists in G-F. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to Õ(f L^{f+o(1)}) and decreases the query time to Õ(f^{5/2} L^{o(1)}), assuming f = o(log L). We also investigate the optimal covering value of any (L,f)-replacement path covering for different parameter ranges and provide a new randomized construction as well as improving a known lower bound; for f = o(log L) we give an RPC with Õ((L/f)^f L^{o(1)})sub

What carries the argument

The method of conditional expectations applied to the randomized Weimann-Yuster subgraph family, which successively fixes random choices while preserving the expected number of useful subgraphs for every possible fault set.

If this is right

  • Deterministic fault-tolerant shortest-path data structures can be constructed with smaller space and faster query times than previous algebraic derandomizations.
  • The same conditional-expectations technique removes the need for error-correcting codes when derandomizing other probabilistic graph coverings.
  • Query times of Õ(f^{5/2} L^{o(1)}) make replacement-path oracles practical for larger graphs when the number of faults is small.
  • The matching upper and lower bounds close the gap on the minimum number of subgraphs needed to cover short replacement paths after f faults.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The conditional-expectations approach may extend to derandomizing other sampling-based coverings in dynamic or directed graphs.
  • For parameter ranges where f is not o(log L) the original randomized bounds or hybrid methods could still be optimal.
  • These coverings could support resilient routing protocols in networks where only a few links are expected to fail.

Load-bearing premise

The regime f = o(log L) is required for the improved query time and for proving that the new randomized covering size is tight.

What would settle it

An explicit graph family in which every (L,f)-RPC, randomized or deterministic, requires asymptotically more than Õ((L/f)^f L^{o(1)}) subgraphs when f = o(log L) would disprove the tightness claim.

read the original abstract

An important tool in the design of fault-tolerant graph data structures are $(L,f)$-replacement path coverings (RPCs). An RPC is a family $\mathcal{G}$ of subgraphs of a given graph $G$ such that, for every set $F$ of at most $f$ edges, there is a subfamily $\mathcal{G}_F \,{\subseteq}\, \mathcal{G}$ with the following properties. (1) No subgraph in $\mathcal{G}_F$ contains an edge of $F$. (2) For each pair of vertices $s,t$ that have a shortest path in $G-F$ with at most $L$ edges, one such path also exists in some subgraph in $\mathcal{G}_F$. The covering value of the RPC is the total number $|\mathcal{G}|$ of subgraphs. The query time is the time needed to compute the subfamily $\mathcal{G}_F$ given the set $F$. Weimann and Yuster [TALG'13] devised a randomized RPC with covering value $\widetilde{O}(fL^f)$ and query time $\widetilde{O}(f^2 L^f)$. This was derandomized by Karthik and Parter [TALG'24], who also reduced the query time to $\widetilde{O}(f^2 L)$. Their approach uses some heavy algebraic machinery involving error-correcting codes and an increased covering value of $O((cfL \log n)^{f+1})$ for some constant $c > 1$. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to $\widetilde{O}(fL^{f+o(1)})$ and decreases the query time to $\widetilde{O}(f^{5/2}L^{o(1)})$, assuming $f = o(\log L)$. We also investigate the optimal covering value of any $(L,f)$-replacement path covering (deterministic or randomized) for different parameter ranges. We provide a new randomized construction as well as improving a known lower bound, also by Karthik and Parter. For example, for $f = o(\log L)$, we give an RPC with $\widetilde{O}( (L/f)^f L^{o(1)})$ subgraphs and show that this is tight up to the $L^{o(1)}$ term.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims a simpler derandomization of (L,f)-replacement path coverings via the conditional-expectations method applied to the Weimann-Yuster randomized RPC. Under the assumption f = o(log L), this yields covering value Õ(f L^{f+o(1)}) and query time Õ(f^{5/2} L^{o(1)}), improving on the algebraic derandomization of Karthik-Parter. The authors also give a new randomized construction with Õ((L/f)^f L^{o(1)}) subgraphs and prove a matching lower bound up to the L^{o(1)} term for the same regime.

Significance. If the results hold, the work provides a valuable simplification by replacing algebraic machinery with an elementary probabilistic method while tightening parameters and establishing near-optimality of the covering value. This strengthens the toolkit for fault-tolerant graph data structures and clarifies the optimal trade-offs in the f = o(log L) regime.

major comments (3)
  1. [§3] §3 (derandomization): The central claim that conditional expectations yields query time Õ(f^{5/2} L^{o(1)}) rests on bounding the number of bad events per step so that the pessimistic estimator can be evaluated efficiently. The manuscript must explicitly derive the 5/2 exponent from this bound and show how f = o(log L) prevents enumeration of an L^f-sized space; without this calculation the query-time improvement is not yet verified.
  2. [§4] §4 (new randomized construction): The claimed Õ((L/f)^f L^{o(1)}) covering value is presented as an improvement, yet the manuscript does not state the precise range of f and L where (L/f)^f is asymptotically smaller than f L^f. A short comparison of the leading terms under f = o(log L) is needed to confirm the improvement is non-vacuous.
  3. [§5] §5 (lower bound): The matching lower bound is stated to be tight up to L^{o(1)} for any RPC. The proof must clarify whether the argument applies directly to randomized coverings (as the new construction is randomized) and must exhibit the exact lower-bound expression so that the o(1) gap can be inspected.
minor comments (2)
  1. All theorems should restate the assumption f = o(log L) explicitly rather than relying on the abstract or introduction.
  2. [Abstract] The abstract refers to 'improving a known lower bound, also by Karthik and Parter'; a one-sentence indication of the quantitative improvement would aid readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and recommendation for minor revision. The comments identify places where additional derivations and comparisons would strengthen the presentation. We address each point below and will incorporate the clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (derandomization): The central claim that conditional expectations yields query time Õ(f^{5/2} L^{o(1)}) rests on bounding the number of bad events per step so that the pessimistic estimator can be evaluated efficiently. The manuscript must explicitly derive the 5/2 exponent from this bound and show how f = o(log L) prevents enumeration of an L^f-sized space; without this calculation the query-time improvement is not yet verified.

    Authors: We agree that the derivation of the query-time bound was insufficiently explicit. In the revised §3 we will add a dedicated paragraph (and supporting lemma) that bounds the number of bad events per conditional-expectation step by O(f^2 L^{o(1)}). The pessimistic estimator for each step is then evaluated by maintaining a priority queue over these events; each extraction and update costs O(f^{1/2} L^{o(1)}) after standard data-structure tricks, yielding an overall per-step cost of O(f^{5/2} L^{o(1)}). Because the method fixes one random bit at a time and the pessimistic estimator depends only on the already-fixed bits plus a local neighborhood of size L^{o(1)}, we never enumerate the full L^f space. The assumption f = o(log L) guarantees that the total number of steps remains sub-exponential in log L, so the aggregate running time stays Õ(f^{5/2} L^{o(1)}). These calculations will be written out in full. revision: yes

  2. Referee: [§4] §4 (new randomized construction): The claimed Õ((L/f)^f L^{o(1)}) covering value is presented as an improvement, yet the manuscript does not state the precise range of f and L where (L/f)^f is asymptotically smaller than f L^f. A short comparison of the leading terms under f = o(log L) is needed to confirm the improvement is non-vacuous.

    Authors: We will insert a short comparison paragraph immediately after the statement of the new construction. For any f ≥ 2 the ratio of the old covering value to the new one is at least f^{f+1} / L^{o(1)}. When f = ω(1) and f = o(log L) this ratio tends to infinity (since f^{f+1} = exp(Θ(f log f)) grows faster than any L^{o(1)} term), establishing an asymptotic improvement. Even for constant f the new bound is smaller by the constant factor f^{f-1}, which is absorbed into the Õ notation but still strictly improves the leading coefficient. The precise regime in which the improvement is asymptotically non-vacuous is therefore all f = o(log L) with f = ω(1); we will state this explicitly. revision: yes

  3. Referee: [§5] §5 (lower bound): The matching lower bound is stated to be tight up to L^{o(1)} for any RPC. The proof must clarify whether the argument applies directly to randomized coverings (as the new construction is randomized) and must exhibit the exact lower-bound expression so that the o(1) gap can be inspected.

    Authors: The lower-bound argument is a pure counting argument: any family of subgraphs (chosen deterministically or randomly) must contain at least Ω((L/f)^f / L^{o(1)}) members to cover all possible f-edge fault sets and all L-edge replacement paths. Because the argument never relies on the particular distribution used to generate the family, it applies verbatim to randomized RPCs; the new randomized construction therefore matches the lower bound up to the L^{o(1)} factor. In the revised §5 we will write the exact lower-bound expression Ω((L/f)^f / L^{o(1)}) and add a sentence clarifying that the proof is distribution-independent. revision: yes

Circularity Check

0 steps flagged

No significant circularity; standard derandomization and independent lower bound

full rationale

The paper begins with the Weimann-Yuster randomized (L,f)-RPC of covering value Õ(f L^f) and applies the standard conditional-expectations method to obtain a deterministic version with covering value Õ(f L^{f+o(1)}) and query time Õ(f^{5/2} L^{o(1)}) when f = o(log L). This is an algorithmic transformation using a well-known technique whose analysis bounds the number of bad events per step; the o(1) term arises from that analysis under the stated regime rather than from any self-referential definition. A separate new randomized construction achieving Õ((L/f)^f L^{o(1)}) is given, together with an improved lower bound (extending Karthik-Parter) showing tightness up to the L^{o(1)} factor. No quantity is defined in terms of another that it is supposed to derive, no parameters are fitted to a data subset and then renamed as a prediction, and no load-bearing claim rests on a self-citation whose authors overlap with the present paper. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard probabilistic method and the method of conditional expectations; no new entities are introduced and no numerical parameters are fitted to data.

axioms (2)
  • domain assumption The method of conditional expectations can be applied to the randomized RPC construction to obtain a deterministic family whose covering value remains Õ(f L^{f+o(1)}).
    This is the central technique invoked for the simpler derandomization.
  • standard math Standard graph-theoretic assumptions (undirected graphs, non-negative edge weights, existence of shortest paths) hold.
    Implicit background for any replacement-path problem.

pith-pipeline@v0.9.0 · 5751 in / 1592 out tokens · 120543 ms · 2026-05-07T04:53:32.000963+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras

    Josh Alman and Dean Hirsch. Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras . In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 9:1--9:19, 2022. https://doi.org/10.4230/LIPIcs.ICALP.2022.9 doi:10.4230/LIPIcs.ICALP.2022.9

    work page doi:10.4230/lipics.icalp.2022.9 2022

  2. [2]

    Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

    Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP) , pages 12:1--12:14, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.12 doi:10.4230/LIPIcs.ICALP.2019.12

    work page doi:10.4230/lipics.icalp.2019.12 2019

  3. [3]

    Approximate Distance Sensitivity Oracles in Subquadratic Space

    Davide Bil \`o , Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Approximate Distance Sensitivity Oracles in Subquadratic Space . TheoretiCS , 3:15:1--15:47, 2024. https://doi.org/10.46298/theoretics.24.15 doi:10.46298/theoretics.24.15

    work page doi:10.46298/theoretics.24.15 2024

  4. [4]

    Improved Distance (Sensitivity) Oracles with Subquadratic Space

    Davide Bil \` o , Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Improved Distance (Sensitivity) Oracles with Subquadratic Space . In Proceedings of the 65th Symposium on Foundations of Computer Science (FOCS) , pages 1550--1558, 2024. https://doi.org/10.1109/FOCS61266.2024.00097 doi:10.1109/FOCS61266.2024.00097

    work page doi:10.1109/focs61266.2024.00097 2024

  5. [5]

    Fault-Tolerant ST-Diameter Oracles

    Davide Bil \` o , Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles . In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 24:1--24:20, 2023. https://doi.org/10.4230/LIPICS.ICALP.2023.24 doi:10.4230/LIPICS.ICALP.2023.24

    work page doi:10.4230/lipics.icalp.2023.24 2023

  6. [6]

    Efficient Fault-Tolerant Search by Fast Indexing of Sub-Networks

    Davide Bil \` o , Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Efficient Fault-Tolerant Search by Fast Indexing of Sub-Networks . In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI) , pages 26463--26471, 2025. https://doi.org/10.1609/AAAI.V39I25.34846 doi:10.1609/AAAI.V39I25.34846

    work page doi:10.1609/aaai.v39i25.34846 2025

  7. [7]

    Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger

    Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger. Fixed-Parameter Sensitivity Oracles . In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS) , pages 23:1--23:18, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.23 doi:10.4230/LIPIcs....

    work page doi:10.4230/lipics.itcs.2022.23 2022

  8. [8]

    Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

    Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances . In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 22:1--22:19, 2022. https://doi.org/10.4230/LIPIcs.ICALP.2022.22 doi:10.4230/...

    work page doi:10.4230/lipics.icalp.2022.22 2022

  9. [9]

    Fault Tolerant Additive and ( \( \) , \( \) )-Spanners

    Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon. Fault Tolerant Additive and ( \( \) , \( \) )-Spanners . Theoretical Computer Science , 580:94--100, 2015. https://doi.org/10.1016/J.TCS.2015.02.036 doi:10.1016/J.TCS.2015.02.036

    work page doi:10.1016/j.tcs.2015.02.036 2015

  10. [10]

    New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures

    Diptarka Chakraborty and Keerti Choudhary. New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures . In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 25:1--25:20, 2020. https://doi.org/10.4230/LIPICS.ICALP.2020.25 doi:10.4230/LIPICS.ICALP.2020.25

    work page doi:10.4230/lipics.icalp.2020.25 2020

  11. [11]

    Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time

    Shiri Chechik and Sarel Cohen. Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time . In Proceedings of the 52nd Symposium on Theory of Computing (STOC) , pages 1375--1388, 2020. https://doi.org/10.1145/3357713.3384253 doi:10.1145/3357713.3384253

    work page doi:10.1145/3357713.3384253 2020

  12. [12]

    ( 1 + )-Approximate f -Sensitive Distance Oracles

    Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. ( 1 + )-Approximate f -Sensitive Distance Oracles . In Proceedings of the 28th Symposium on Discrete Algorithms (SODA) , pages 1479--1496, 2017. https://doi.org/10.1137/1.9781611974782.96 doi:10.1137/1.9781611974782.96

    work page doi:10.1137/1.9781611974782.96 2017

  13. [13]

    f -Sensitivity Distance Oracles and Routing Schemes

    Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f -Sensitivity Distance Oracles and Routing Schemes . Algorithmica , 63:861--882, 2012. https://doi.org/10.1007/s00453-011-9543-0 doi:10.1007/s00453-011-9543-0

    work page doi:10.1007/s00453-011-9543-0 2012

  14. [14]

    Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

    Kyungjin Cho, Jihun Shin, and Eunjin Oh. Approximate Distance Oracle for Fault-Tolerant Geometric Spanners . In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , pages 20087--20095, 2024. https://doi.org/10.1609/aaai.v38i18.29987 doi:10.1609/aaai.v38i18.29987

    work page doi:10.1609/aaai.v38i18.29987 2024

  15. [15]

    On Packing Low-Diameter Spanning Trees

    Julia Chuzhoy, Merav Parter, and Zihan Tan. On Packing Low-Diameter Spanning Trees . In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 33:1--33:18, 2020. https://doi.org/10.4230/LIPICS.ICALP.2020.33 doi:10.4230/LIPICS.ICALP.2020.33

    work page doi:10.4230/lipics.icalp.2020.33 2020

  16. [16]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of Information Theory . Wiley Series in Telecommunications and Signal Processing. Wiley-Interscience, New York City, NY, USA, 2nd edition, 2006. https://doi.org/10.1002/047174882X doi:10.1002/047174882X

    work page doi:10.1002/047174882x 2006

  17. [17]

    Oracles for distances avoiding a failed node or link.SIAM Journal on Computing, 37(5):1299–1318, 2008

    Camil Demetrescu, Mikkel Thorup, Rezaul A. Chowdhury, and Vijaya Ramachandran. Oracles for Distances Avoiding a Failed Node or Link . SIAM Journal on Computing , 37:1299--1318, 2008. https://doi.org/10.1137/S0097539705429847 doi:10.1137/S0097539705429847

    work page doi:10.1137/s0097539705429847 2008

  18. [18]

    Nearly Optimal Fault Tolerant Distance Oracle

    Dipan Dey and Manoj Gupta. Nearly Optimal Fault Tolerant Distance Oracle . In Proceedings of the 56th Symposium on Theory of Computing (STOC) , pages 944--955, 2024. https://doi.org/10.1145/3618260.3649697 doi:10.1145/3618260.3649697

    work page doi:10.1145/3618260.3649697 2024

  19. [19]

    Fault-Tolerant Spanners: Better and Simpler

    Michael Dinitz and Robert Krauthgamer. Fault-Tolerant Spanners: Better and Simpler . In Proceedings of the 30th Symposium on Principles of Distributed Computing (PODC) , pages 169--178, 2011. https://doi.org/10.1145/1993806.1993830 doi:10.1145/1993806.1993830

    work page doi:10.1145/1993806.1993830 2011

  20. [20]

    Efficient and Simple Algorithms for Fault-Tolerant Spanners

    Michael Dinitz and Caleb Robelle. Efficient and Simple Algorithms for Fault-Tolerant Spanners . In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC) , page 493–500, 2020. https://doi.org/10.1145/3382734.3405735 doi:10.1145/3382734.3405735

    work page doi:10.1145/3382734.3405735 2020

  21. [21]

    Dual-Failure Distance and Connectivity Oracles

    Ran Duan and Seth Pettie. Dual-Failure Distance and Connectivity Oracles . In Proceedings of the 20th Symposium on Discrete Algorithms (SODA) , pages 506--515, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496826

    work page arXiv 2009

  22. [22]

    Connectivity Oracles for Failure Prone Graphs

    Ran Duan and Seth Pettie. Connectivity Oracles for Failure Prone Graphs . In Proceedings of the 42nd Symposium on Theory of Computing (STOC) , pages 465--474, 2010. https://doi.org/10.1145/1806689.1806754 doi:10.1145/1806689.1806754

    work page doi:10.1145/1806689.1806754 2010

  23. [23]

    Connectivity Oracles for Graphs Subject to Vertex Failures

    Ran Duan and Seth Pettie. Connectivity Oracles for Graphs Subject to Vertex Failures . In Proceedings of the 28th Symposium on Discrete Algorithms (SODA) , pages 490--509, 2017. https://doi.org/10.1137/17M1146610 doi:10.1137/17M1146610

    work page doi:10.1137/17m1146610 2017

  24. [24]

    Maintaining Exact Distances under Multiple Edge Failures

    Ran Duan and Hanlin Ren. Maintaining Exact Distances under Multiple Edge Failures . In Proceedings of the 54th Symposium on Theory of Computing (STOC) , pages 1093--1101, 2022. https://doi.org/10.1145/3519935.3520002 doi:10.1145/3519935.3520002

    work page doi:10.1145/3519935.3520002 2022

  25. [25]

    Faster Replacement Paths and Distance Sensitivity Oracles , journal =

    Fabrizio Grandoni and Virginia Vassilevska Williams . Faster Replacement Paths and Distance Sensitivity Oracles . ACM Transaction on Algorithms , 16:15:1--15:25, 2020. https://doi.org/10.1145/3365835 doi:10.1145/3365835

    work page doi:10.1145/3365835 2020

  26. [26]

    Constructing a Distance Sensitivity Oracle in O(n

    Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^ 2.5794 M) Time . In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 76:1--76:20, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.76 doi:10.4230/LIPIcs.ICALP.2021.76

    work page doi:10.4230/lipics.icalp.2021.76 2021

  27. [27]

    Conditional Hardness for Sensitivity Problems

    Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams . Conditional Hardness for Sensitivity Problems . In Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS) , pages 26:1--26:31, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.26 doi:10.4230/LIPIcs.ITCS.2017.26

    work page doi:10.4230/lipics.itcs.2017.26 2017

  28. [28]

    Broadcast CONGEST Algorithms against Adversarial Edges

    Yael Hitron and Merav Parter. Broadcast CONGEST Algorithms against Adversarial Edges . In Proceedings of the 35th Symposium on Distributed Computing (DISC) , pages 23:1--23:19, 2021. https://doi.org/10.4230/LIPICS.DISC.2021.23 doi:10.4230/LIPICS.DISC.2021.23

    work page doi:10.4230/lipics.disc.2021.23 2021

  29. [29]

    Karthik C. S. and Merav Parter. Deterministic Replacement Path Covering . ACM Transactions on Algorithms , 20:34:1--34:35, 2024. https://doi.org/10.1145/3673760 doi:10.1145/3673760

    work page doi:10.1145/3673760 2024

  30. [30]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, Cambridge, NY, USA, 1995. https://doi.org/10.1017/CBO9780511814075 doi:10.1017/CBO9780511814075

    work page doi:10.1017/cbo9780511814075 1995

  31. [31]

    Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

    Merav Parter. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach . In Proceedings of the 33rd Symposium on Distributed Computing (DISC) , pages 30:1--30:16, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.30 doi:10.4230/LIPICS.DISC.2019.30

    work page doi:10.4230/lipics.disc.2019.30 2019

  32. [32]

    Low Congestion Cycle Covers and Their Applications

    Merav Parter and Eylon Yogev. Low Congestion Cycle Covers and Their Applications . In Proceedings of the 30th Symposium on Discrete Algorithms (SODA) , pages 1673--1692, 2019. https://doi.org/10.1137/1.9781611975482.101 doi:10.1137/1.9781611975482.101

    work page doi:10.1137/1.9781611975482.101 2019

  33. [33]

    Secure Distributed Computing Made (Nearly) Optimal

    Merav Parter and Eylon Yogev. Secure Distributed Computing Made (Nearly) Optimal . In Proceedings of the 38th Symposium on Principles of Distributed Computing (PODC) , pages 107--116, 2019. https://doi.org/10.1145/3293611.3331620 doi:10.1145/3293611.3331620

    work page doi:10.1145/3293611.3331620 2019

  34. [34]

    Planning for Fast Connectivity Updates

    Mihai Patrascu and Mikkel Thorup. Planning for Fast Connectivity Updates . In Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS) , pages 263--271, 2007. https://doi.org/10.1109/FOCS.2007.59 doi:10.1109/FOCS.2007.59

    work page doi:10.1109/focs.2007.59 2007

  35. [35]

    Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication

    Oren Weimann and Raphael Yuster. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication . ACM Transactions on Algorithms , 9:14:1--14:13, 2013. https://doi.org/10.1145/2438645.2438646 doi:10.1145/2438645.2438646

    work page doi:10.1145/2438645.2438646 2013