Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

Merav Parter

REVIEW 3 major objections 5 minor 31 references

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves that exact minimum cuts in constant-edge-connected graphs can be computed deterministically in poly(D) distributed rounds, making small cuts a local problem.

desk verdict Strong paper with a real but repairable gap: the min-cut theorems need a log n factor to get the claimed high-probability bound, so the headline poly(D) is slightly overstated. read the letter →

arxiv 1908.03022 v2 pith:KVVULNPA submitted 2019-08-08 cs.DS cs.DC

Merav Parter This is my paper · ORCID

classification cs.DScs.DC MSC 68W1568W2005C4068R1005C85

keywords distributedminimumcutCONGESTmodeledgeconnectivitycertificatesfault-tolerantsamplinguniversalsetslow-congestioncyclecoversspanners

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

The paper claims that three distributed connectivity problems become local once the connectivity is constant: exact minimum cut, all edge connectivities up to a constant, and sparse connectivity certificates. Its main theorem gives a deterministic algorithm that, in any unweighted $D$-diameter graph with constant edge connectivity $\lambda$, finds an exact minimum cut in $\mathrm{poly}(D)$ CONGEST rounds, matching the known $\Omega(D)$ lower bound up to polynomial factors; the randomized version even finds every minimum cut. The same fault-tolerant sampling idea, combined with low-congestion cycle covers, computes all edge connectivities up to constant $\lambda$ in $\mathrm{poly}(D)\cdot 2^{O(\sqrt{\log n \log\log n})}$ rounds, and a simple observation---that fault-tolerant spanners are connectivity certificates---yields $\lambda$-sparse certificates in $O(\lambda \log^{1+o(1)} n)$ rounds. A reader should care because these problems were previously thought to require global communication depending on $n$ (roughly $D+\sqrt{n}$ rounds), and the paper shows the small-connectivity regime is essentially local.

What carries the argument

The load-bearing object is the $(s,t)$ connectivity certificate, a subgraph $G_{s,t}$ that preserves $s$-$t$ $\lambda$-connectivity, and the load-bearing lemma is the distance bound of Lemma 6: in a $D$-diameter graph, removing at most $\lambda - 1$ faults leaves any $\lambda$-connected pair at distance $O(\lambda D)$, because the faulted BFS forest splits into at most $\lambda$ components, each of diameter $O(D)$. This bound makes truncated BFS search up to depth $c\lambda D$ sufficient to find an $s$-$t$ path in $G \setminus F$, and it controls the path length a sampled subgraph must keep. The FT-universal set is the deterministic replacement for sampling: a small explicit family of subgraphs such that for every disjoint pair $(A,B)$ with $|A| \le c\lambda D$ and $|B| \le \lambda$, some member contains all of $A$ and none of $B$, which reproduces the successful-sample event for every fault set simultaneously. For all edge connectivities, the additional machinery is the low-congestion cycle cover: a collection of short cycles covering each edge with bounded per-edge congestion, used to certify that around any fault set a $u$-$v$ path survives inside the collected cycle union.

What would settle it

Implement the cycle-cover subroutine of Corollary 20 on a $D$-diameter graph in which a chosen edge $e$ lies on a cycle of length at most $D'$ but on no shorter cycle, and inspect the returned collection: if $e$ is not covered by some cycle of length at most $2^{O(\sqrt{\log n})} \cdot |C_e|$ with per-edge congestion at most $2^{O(\sqrt{\log n})}$, the coverage guarantee that Claim 21 relies on has failed, and the all-edge-connectivity theorem has no certificate for that edge.

Watch

Extended reading notes

Core claim

The central discovery is that the minimum cut of a constant-edge-connected graph can be recovered from a small collection of random subgraphs. For a fixed source $s$, the algorithm samples $\tau = (c\lambda D)^{2\lambda}$ subgraphs by keeping each edge with probability $1 - 1/(c\lambda D)$, and in each one runs a BFS tree truncated at depth $c\lambda D$; for each vertex $t$ it records the $s$-$t$ path when it exists. The proof shows that with high probability the union of these recorded paths over all $\tau$ samples is an $(s,t)$ connectivity certificate: for every fault set $F$ of at most $\lambda - 1$ edges that leaves $s$ and $t$ connected, some sampled subgraph contains a short $s$-$t$ path avoiding $F$ and excludes $F$, so the certificate preserves exactly which pairs are $\lambda$-connected. Each vertex $t$ then locally computes the $s$-$t$ minimum cut in its own certificate and broadcasts the $\lambda$-edge cut it finds. The same certificate logic works for every pair $(u,v)$ when the recorded objects are cycles instead of paths, using low-congestion cycle covers to find a $u$-$v$ path around any fault set, which yields all edge connectivities. Determinism is obtained by replacing the random subgraphs with an explicit family of FT-universal sets, constructed in polynomial time from perfect hash functions, that guarantees the same separation property for every relevant pair of path and fault set.

Load-bearing premise

The load-bearing premise is that the low-congestion cycle-cover subroutine (a set of short cycles covering every edge, with each edge appearing on few cycles) delivers its stated guarantee for every relevant edge: if some edge that lies on a short cycle is not covered by a cycle of the promised length and congestion, then the certificate argument of Claim 21 collapses and with it the all-edge-connectivities theorem.

Editorial extensions

If this is right

The minimum cut of any constant-edge-connected $D$-diameter graph can be found deterministically in $\mathrm{poly}(D)$ rounds, so the small-cut regime has no hidden dependence on $n$ and matches the $\Omega(D)$ lower bound up to polynomial factors.
The randomized min-cut algorithm outputs every minimum cut in the sense that for each min-cut set $E'$, at least one vertex learns exactly $E'$, and every vertex $t$ also learns $\lambda-1$ edge-disjoint paths from the chosen source $s$.
All edge connectivities up to a constant can be learned by the endpoints of every edge in $\mathrm{poly}(D)\cdot 2^{O(\sqrt{\log n \log\log n})}$ rounds, improving the previous $\lambda \le 2$ bounds with $O(D)$ or $O(D+\sqrt{n}\log^* n)$ rounds.
Sparse $\lambda$-connectivity certificates with $O(\lambda n)$ edges can be computed in $O(\lambda \log^{1+o(1)} n)$ rounds, and $(1-\epsilon)\lambda$-certificates in $O(1/\epsilon^2 \log^{2+o(1)} n)$ rounds, so certificate construction is independent of diameter.
The FT-universal-set derandomization applies to any algorithm based on fault-tolerant sampling, turning randomized sampling-based constructions into deterministic ones with the same asymptotic round count.

Reading between the lines

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

The sampling-plus-certificate view suggests that other global problems whose only obstacle is an $\Omega(D)$ lower bound may become $\mathrm{poly}(D)$-solvable when a parameter like connectivity or degree is constant; the paper's vertex-cut version ($\mathrm{poly}(D\cdot \Delta)$) is a first instance of the degree entering the cost.
The FT-universal-set construction is a general derandomization primitive: plugging it into centralized FT-sampling algorithms for replacement paths and distance sensitivity oracles should make those deterministic without changing their asymptotic complexity, which the paper notes but does not develop.
The observation that fault-tolerant spanners are connectivity certificates turns the two fields into each other's lower-bound machinery: any improved local FT-spanner construction automatically improves sparse certificates, and any certificate lower bound would transfer to FT-spanners.
The Karger-style decomposition behind the $(1-\epsilon)\lambda$ certificates suggests a clean picture: for very large connectivity the problem is polylogarithmic, for constant connectivity the min-cut problem is $\mathrm{poly}(D)$, and the intermediate regime between constant and $\sqrt{n}$ likely hides the true global hardness.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

This is a good paper. The main result—an exact distributed min-cut algorithm for constant connectivity that runs in poly(D, log n) and answers the DHNS19 open problem—is real and the technique is genuinely novel. The idea of treating the min cut as a fault-tolerance problem, sampling subgraphs so that any failure set is avoided while a surviving path is kept, is elegant. The same lens yields sparse connectivity certificates from FT-spanners, which is a short clean observation, and the FT-universal sets derandomization is likely to be reused beyond this paper. The math in Sections 2 and 4 mostly checks out.

That said, there are three soft spots, and the first is the most serious. Claim 9's union bound is off by a log n factor. With ℓ = (λD)^{2λ} iterations, the probability that a fixed triplet has no successful iteration is (1 − q)^ℓ where q = 1/(λD)^λ, so for constant λD that probability is constant, not n^{−Ω(λ)}. You need ℓ = poly(D) log n to get high probability, which changes the round bound to poly(D, log n). The same issue infects the deterministic construction: the explicit FT-universal family of Lemma 17 has size ~O((4a)^{O(1)+2b}) but the perfect hash family contributes a log n factor, and a simple signature argument shows some log factor is unavoidable. So Theorems 1 and 2 overclaim pure poly(D), but the stated open problem—poly(k, D, log n)—is still answered. Fix is easy: restate with the log factor.

The 'all minimum cuts' claim also isn't supported by the proof. Each vertex t discovers some min s-t cut in its certificate, but the argument doesn't show that every global min cut E' is output by some vertex. The vertex-cut version with multiple sources has the same issue. This looks fixable by adding a careful argument about which cuts are recovered, or by weakening the claim.

The all-edge-connectivities algorithm in Section 3 has a bridge problem: for a bridge e, no cycle contains e, so G_{u,v} is empty and the pseudocode outputs 0 instead of 1. That's a small bug. The cycle-cover subroutine (Corollary 20) is only sketched, but it comes from published work, so I don't regard that as a fatal weakness; just note Claim 21 doesn't fold in its w.h.p. failure probability.

Bottom line: the core contribution is sound in spirit and the flaws are repairable. Send it to a serious referee. I'd bring it to the reading group.

Referee Report

3 major / 5 minor

Summary. The paper presents distributed CONGEST algorithms for three problems: exact minimum cut in graphs of constant edge connectivity, computation of all edge connectivities up to a constant, and sparse connectivity certificates. The main randomized min-cut algorithm fixes a source s, performs repeated independent edge-sampling experiments, and in each experiment computes a truncated BFS tree of depth O(lambda D); each vertex t then locally computes a min cut in the union of its sampled s-t paths. The paper also gives a deterministic version based on a new notion of FT-universal sets, and a certificate algorithm based on fault-tolerant spanners and Karger edge sampling. The headline claims are poly(D) rounds for randomized and deterministic exact min cut, poly(D) * 2^{O(sqrt(log n))} for all connectivities, and O~(lambda) / O(eps^{-2} log^{2+o(1)} n) for certificates.

Significance. The paper's high-level approach is appealing and several components are genuinely useful: Lemma 6 (short paths after few edge deletions in a D-diameter graph) is clean; the FT-universal-set derandomization, once the size bound is corrected, is a reusable idea; and Observation 25 (FT-spanners are connectivity certificates) gives a simple route to sparse certificates. If the complexity statements are corrected to allow a log n factor, the results still answer the DHNS19 question and improve prior certificate constructions. The errors identified below affect the strongest stated round-complexity claims but not the core sampling and certificate arguments.

major comments (3)

[Section 2, Claim 9] The iteration count does not give the claimed w.h.p. guarantee when D=O(1). The proof sets p=1-1/(c lambda D), so q=p^{c lambda D}(1-p)^lambda = Theta((lambda D)^{-lambda}); with ell=O((lambda D)^{2 lambda}) the per-triplet failure probability is (1-q)^ell <= exp(-Theta((lambda D)^lambda)), which is a constant for D=O(1). The union bound over n^{2 lambda} triplets therefore yields constant * n^{2 lambda}, not n^{-Omega(lambda)}. A concrete instance is a star (D=2, lambda=1): the unique bridge is missed by all ell=O(1) experiments with constant probability, and the affected leaf outputs the empty cut. The randomized algorithm and Theorem 1 should be restated with ell multiplied by a log n factor, i.e., poly(D, log n) or O~(poly(D)) rounds.
[Section 2.1, Lemma 17 and Theorem 2] The claimed family size is too small for D=O(1), so the deterministic poly(D) claim is not supported. For b=1 and a>=1, Definition 12 applied to A={e}, B={f} for every ordered pair of distinct edges requires a family member containing e and avoiding f; hence every edge has a distinct membership signature and any (n,a,b)-universal family has size at least log m = Omega(log n). Lemma 17's bound O~((4a)^{O(1)+2b}) is only correct with the polylog n hidden in the tilde, and the deterministic min-cut algorithm built on this family needs Omega(log n) iterations on a star (D=2, lambda=1). Theorem 2 should therefore be weakened to poly(D, log n) or O~(poly(D)) unless a different derandomization is provided.
[Section 2, paragraph after Theorem 1] The 'all minimum cuts' claim is not established by the proof. The correctness argument shows that any cut F locally computed by a vertex t is indeed a cut of G; it does not show that a prescribed minimum cut E' is output by some vertex when G_{s,t} contains several minimum s-t cuts. To support the advertised statement, the algorithm must either enumerate all minimum cuts of G_{s,t} and have each vertex broadcast them, or prove that the chosen min cut is the desired E'; neither is present.

minor comments (5)

[Section 3 / Figure 1] The iteration count in the text (ell = O(lambda D^lambda log n)) differs from the loop in the pseudocode (O(lambda D)^{2 lambda}); please unify and state the success probability explicitly.
[Section 3 / Figure 1] The sampling probability is written as p = 1 - 1/(D')^lambda in the text but p = 1 - 1/D' in Figure 1; these give different guarantees and should be reconciled.
[Fact 15] The citation '[Vad12, ?]' contains a stray '?' and should be completed.
[Lemma 27] The lemma states epsilon in [0,1], but the proof and Lemma 5 require epsilon in (0,1); please correct the range.
[Abstract] The abstract contains the typo 'resolves one the open problems'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the min-cut, all-connectivities, and certificate proofs derive their conclusions from independent sampling, distance, and hashing ingredients; the flagged log n gap is a correctness issue, not a circular one.

full rationale

The paper's central claims are algorithmic upper bounds; none is obtained by fitting a parameter to the quantity it claims to predict, and the outputs (min cuts, edge connectivities, certificates) are not used as inputs to their own derivations. The randomized min-cut proof (Section 2, Claim 9) derives the certificate G_{s,t} as the union of sampled BFS paths; the witnesses are the path A and fault set B, and the proof uses the independent distance bound of Lemma 6 plus a union bound. Even though the iteration count appears to omit a log n factor for D=O(1) (so the w.h.p. guarantee is not established as stated), that is a probabilistic correctness gap, not a reduction of the theorem to its assumptions. The deterministic version constructs FT-universal families satisfying exactly the required separation property; their existence is proved by the probabilistic method and then by an explicit perfect-hash construction from external Fact 15, so the universal set is not defined in terms of the min cut. Section 3 imports the low-congestion cycle covers of [PY19a]/[PY19b]; these are published, standalone cycle-length/congestion results whose guarantees do not include the all-edge-connectivity theorem, and Claim 21 derives the connectivity certificate by combining them with the same sampling argument. The sparse-certificate results derive certificates from FT-spanners via Observation 25, using external spanner algorithms (Pettie, CLPR10, DK11, Karger sampling) rather than assuming the certificate. Consequently, no step is equivalent by construction to its own input; the only flagged weaknesses (the log n gap in Claim 9/Lemma 17 and the malformed '[Vad12, ?]' citation) are correctness or completeness issues outside circularity.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new physical entities. Its new mathematical object, FT-universal sets, is a definition with explicit constructions and proofs, not a postulated entity. All other assumptions are standard mathematical tools or prior published results; the central claims are not fitted to any dataset.

free parameters (4)

sampling probability p = 1 - 1/(c*lambda*D)
Chosen so that a successful iteration has probability Omega((lambda D)^{-lambda}); an algorithmic design constant, not fitted to data.
number of iterations ell = (lambda D)^{2lambda} * log n
Set by the union bound over the relevant triplets; a proof-driven choice, not fitted.
cycle cover length parameter D' = 2c*lambda*D + 1
Set to exceed the fault-tolerant path length bound from Lemma 6; a design choice.
number of edge-sampling subgraphs mu = ceil(lambda * epsilon^2 / (20 log n))
Karger's sampling parameter chosen to keep each subgraph's connectivity near Theta(log n / epsilon^2).

assumptions (7)

domain assumption CONGEST model: per round each node sends O(log n) bits per incident edge; local computation is unbounded.
All round-complexity claims are relative to this model, stated in 'The Communication Model' section.
standard math Menger's theorem: edge/vertex connectivity equals the maximum number of edge/vertex-disjoint paths.
Used implicitly in cut-verification and certificate definitions, e.g., Definition 8 and Claim 9.
domain assumption Karger's edge-sampling theorem: sampling edges with probability p preserves edge connectivity within (1 +/- epsilon) lambda / mu w.h.p. for lambda = Omega(log n).
Used in Lemma 27 to split the graph into mu subgraphs; imported from [Kar99].
domain assumption Low-congestion cycle cover bounds of PY19a/PY19b and the randomized ApproxCycleCover of Corollary 20: every edge on a cycle of length L is covered by a cycle of length 2^{O(sqrt(log n))} * L with congestion 2^{O(sqrt(log n))}, computable in 2^{O(sqrt(log n))} * D' rounds.
The all-edge-connectivities algorithm (Theorem 3) depends on this; the paper gives only a proof sketch in Section 3.
domain assumption Explicit families of epsilon-almost pairwise independent hash functions with poly(alpha * 2^beta / epsilon) functions computable in polynomial time.
Used in Claim 16 to build perfect hash families for FT-universal sets; cited to [Vad12] with a placeholder reference.
domain assumption Fault-tolerant spanner transformations: CLPR10 converts a spanner algorithm into an f-edge-FT spanner with O(f * n^{1+1/k}) edges in O(f * t) time; DK11 gives the vertex-fault analog.
Observation 26 turns these into distributed sparse certificates; imported from [CLPR10, DK11].
domain assumption Pettie's ultra-sparse spanner: O(n) edges, stretch O(log n), O(log^{1+o(1)} n) distributed rounds.
Used in Observation 26 and Lemma 27; cited to [Pet10].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Small Cuts and Connectivity Certificates: A Fault Tolerant Approach." pith.science (2026). https://pith.science/paper/KVVULNPA

@misc{pith2026190803022,
  author       = {Pith},
  title        = {Pith review of: Small Cuts and Connectivity Certificates: A Fault Tolerant Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KVVULNPA}},
  note         = {Machine review of arXiv:1908.03022}
}

abstract

We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even "local" (i.e., with $\widetilde{O}(1)$ rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of $\Omega(Diam+\sqrt{n})$ rounds). Our main results are: (1) For $D$-diameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in $poly(D)$ rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOC'19. (2) For $D$-diameter unweighted graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in $poly(D)\cdot 2^{O(\sqrt{\log n\log\log n})}$ rounds. (3) Computation of sparse $\lambda$ connectivity certificates in $\widetilde{O}(\lambda)$ rounds. Previous constructions where known only for $\lambda \leq 3$ and required $O(D)$ rounds. This resolves the problem raised by Dori PODC'18.

Figures

Figures reproduced from arXiv: 1908.03022 by the authors.

**Figure 1.** Distributed Computation of λ-edge connected cycle covers 4 Sparse Connectivity Certificates Finally, we consider the related problem of computing sparse connectivity certificates. We start by observing that an FT-spanner for the graph is also a connectivity certificate. Fault Tolerant Spanners. Fault tolerant (FT) spanners [LNS98, CLPR10] are sparse subgraphs that preserve pairwise distances in G (up to some multip… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 28 canonical work pages

[1]

Explicit construction of exponential sized families of k-independent sets

Noga Alon. Explicit construction of exponential sized families of k-independent sets. Discrete Mathematics , 58(2):191--193, 1986

work page 1986
[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 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. , pages 12:1--12:14, 2019

work page 2019
[3]

Fast distributed approximation for TAP and 2-edge-connectivity

Keren Censor - Hillel and Michal Dory. Fast distributed approximation for TAP and 2-edge-connectivity. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017 , pages 21:1--21:20, 2017

work page 2017
[4]

Fault tolerant spanners for general graphs

Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM Journal on Computing , 39(7):3403--3423, 2010

work page 2010
[5]

Distributed edge connectivity in sublinear time

Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Saranurak. Distributed edge connectivity in sublinear time. In STOC , 2019

work page 2019
[6]

Fault-tolerant spanners: better and simpler

Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 169--178. ACM, 2011

work page 2011
[7]

Distributed approximation of minimum k-edge-connected spanning subgraphs

Michal Dory. Distributed approximation of minimum k-edge-connected spanning subgraphs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018 , pages 149--158, 2018

work page 2018
[8]

On mixed connectivity certificates

Shimon Even, Gene Itkis, and Sergio Rajsbaum. On mixed connectivity certificates. Theor. Comput. Sci. , 203(2):253--269, 1998

work page 1998

Show all 31 references

[9]

Constructing o (n log n) size monotone formulae for the k-th elementary symmetric polynomial of n boolean variables

J Friedman. Constructing o (n log n) size monotone formulae for the k-th elementary symmetric polynomial of n boolean variables. In Foundations of Computer Science, 1984. 25th Annual Symposium on , pages 506--515. IEEE, 1984

1984
[10]

Improved Distributed Algorithms for Fundamental Graph Problems

Mohsen Ghaffari. Improved Distributed Algorithms for Fundamental Graph Problems . PhD thesis, MIT, USA , 2017. URL: https://groups.csail.mit.edu/tds/papers/Ghaffari/PhDThesis-Ghaffari.pdf

2017
[11]

Distributed minimum cut approximation

Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In International Symposium on Distributed Computing , pages 1--15. Springer, 2013

2013
[12]

Distributed minimum cut approximation

Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. arXiv preprint arXiv:1305.5520 , 2013

2013 arXiv
[13]

Derandomizing distributed algorithms with small messages: Spanners and dominating set

Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018 , pages 29:1--29:17, 2018

2018
[14]

Random sampling in cut, flow, and network design problems

David R Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research , 24(2):383--413, 1999

1999
[15]

Efficient algorithms for constructing fault-tolerant geometric spanners

Christos Levcopoulos, Giri Narasimhan, and Michiel Smid. Efficient algorithms for constructing fault-tolerant geometric spanners. In Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages 186--195. ACM, 1998

1998
[16]

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph. Algorithmica , 7(1-6):583--596, 1992

1992
[17]

Almost-tight distributed minimum cut algorithms

Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing , pages 439--453. Springer, 2014

2014
[18]

Low congestion cycle covers and their applications

Merav Parter and Eylon Yogev. Low congestion cycle covers and their applications. SODA , 2019

2019
[19]

Optimal short cycle decomposition in almost linear time

Merav Parter and Eylon Yogev. Optimal short cycle decomposition in almost linear time. ICALP , 2019

2019
[20]

Distributed Computing: A Locality-sensitive Approach

David Peleg. Distributed Computing: A Locality-sensitive Approach . SIAM, 2000

2000
[21]

Distributed algorithms for ultrasparse spanners and linear size skeletons

Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing , 22(3):147--166, 2010. URL: https://doi.org/10.1007/s00446-009-0091-7, http://dx.doi.org/10.1007/s00446-009-0091-7 doi:10.1007/s00446-009-0091-7

2010 doi
[22]

Fast computation of small cuts via cycle space sampling

David Pritchard and Ramakrishna Thurimella. Fast computation of small cuts via cycle space sampling. ACM Transactions on Algorithms (TALG) , 7(4):46, 2011

2011
[23]

Polylogarithmic-time deterministic network decomposition and distributed derandomization

V \' a clav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. arXiv preprint arXiv:1907.10937 , 2019

1907 arXiv
[24]

Distributed verification and hardness of distributed approximation

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing , 41(5):1235--1265, 2012

2012
[25]

Sub-linear distributed algorithms for sparse certificates and biconnected components

Ramakrishna Thurimella. Sub-linear distributed algorithms for sparse certificates and biconnected components. Journal of Algorithms , 23(1):160--179, 1997

1997
[26]

Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science , 7(1–3):1--336, 2012. URL: http://dx.doi.org/10.1561/0400000010, http://dx.doi.org/10.1561/0400000010 doi:10.1561/0400000010

2012 doi
[27]

Complex networks: small-world, scale-free and beyond

Xiao Fan Wang and Guanrong Chen. Complex networks: small-world, scale-free and beyond. IEEE circuits and systems magazine , 3(1):6--20, 2003

2003
[28]

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 (TALG) , 9(2):14, 2013

2013
[29]

Improved Distributed Algorithms for Fundamental Graph Problems

Mohsen Ghaffari. Improved Distributed Algorithms for Fundamental Graph Problems . PhD thesis, MIT, USA , 2017

2017
[30]

Distributed algorithms for ultrasparse spanners and linear size skeletons

Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing , 22(3):147--166, 2010

2010
[31]

Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science , 7(1–3):1--336, 2012

2012

Pith tools

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

[1] [1]

Explicit construction of exponential sized families of k-independent sets

Noga Alon. Explicit construction of exponential sized families of k-independent sets. Discrete Mathematics , 58(2):191--193, 1986

work page 1986

[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 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. , pages 12:1--12:14, 2019

work page 2019

[3] [3]

Fast distributed approximation for TAP and 2-edge-connectivity

Keren Censor - Hillel and Michal Dory. Fast distributed approximation for TAP and 2-edge-connectivity. In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017 , pages 21:1--21:20, 2017

work page 2017

[4] [4]

Fault tolerant spanners for general graphs

Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM Journal on Computing , 39(7):3403--3423, 2010

work page 2010

[5] [5]

Distributed edge connectivity in sublinear time

Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Saranurak. Distributed edge connectivity in sublinear time. In STOC , 2019

work page 2019

[6] [6]

Fault-tolerant spanners: better and simpler

Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 169--178. ACM, 2011

work page 2011

[7] [7]

Distributed approximation of minimum k-edge-connected spanning subgraphs

Michal Dory. Distributed approximation of minimum k-edge-connected spanning subgraphs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018 , pages 149--158, 2018

work page 2018

[8] [8]

On mixed connectivity certificates

Shimon Even, Gene Itkis, and Sergio Rajsbaum. On mixed connectivity certificates. Theor. Comput. Sci. , 203(2):253--269, 1998

work page 1998