{"id":"f7863b63-3d75-45f2-9569-8ed76923d5de","arxiv_id":"1908.03022","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"For constant-connectivity networks, exact minimum cut is computed in poly(diameter) rounds, all edge connectivities up to a constant in poly(diameter) times 2^{O(sqrt(log n log log n))}, and sparse certificates in almost O(1) rounds.","lead":"This paper solves a long-open distributed computing problem: finding the minimum cut of a network with constant connectivity in time that depends only on the network's diameter. It also makes randomized sampling techniques deterministic and builds sparse connectivity certificates in almost constant time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 9's iteration count omits a log n factor: for D=O(1), the failure probability is constant, so the advertised poly(D) w.h.p. min-cut guarantee is not established.","rationale":"The reader's weakest-assumption pick, Corollary 20/Claim 21 concerning the cycle cover, is a legitimate concern but it affects Theorem 3, the all-edge-connectivities extension. My concern is more central: it hits the main headline result, exact minimum cut in poly(D) rounds, and it is internal to the paper's own probability calculation and universal-set construction. I verified the per-iteration success probability q in Claim 9; the issue is not the sampling probability but the absence of a log n factor in the number of iterations. For constant diameter, exp(-(\\lambda D)^{\\lambda}) is a fixed constant, not a polynomial-in-n tail, so the claimed n^{-\\Omega(\\lambda)} bound cannot follow. The deterministic version cannot dodge this by using Lemma 17, because any family satisfying Def. 12 with b=1 must have at least logarithmic size: each set gives one bit of a signature, and the family must separate every pair of edges. This lower bound is elementary and parameter-free, so the polylog n factor in Claim 16 is not an artifact of a particular construction. Because the paper's methods still resolve the Daga et al. open problem if the statement is weakened to poly(D, log n), I would not reject the paper; the correct verdict remains conditional, but for a more fundamental reason than the reader's stated weakest assumption.","tokens_in":16026,"tokens_out":22006,"duration_ms":259109,"concrete_test":"Test the missing log n factor directly: take two cliques joined by a single bridge (\\lambda=1, D=3) and let n grow arbitrarily. Using the paper's own parameters, compute the probability that the bridge is absent from all \\ell = c(\\lambda D)^{2\\lambda} = O(1) sampled subgraphs; the closed form is (1/(c\\lambda D))^{\\ell}, a constant independent of n, so for n large enough this constant exceeds n^{-1}, contradicting the n^{-\\Omega(\\lambda)} claim in Claim 9. As a companion check, verify the signature lower bound for Def. 12 with b=1: every pair of edges must receive distinct membership signatures over the family, forcing \\Omega(\\log n) sets; if both checks hold, Theorems 1 and 2 require a \\log n factor in the round bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central min-cut theorems (Theorems 1 and 2) are not supported by the stated experiment count. In Section 2, Claim 9 fixes a triplet <s,t,F> and an iteration succeeds with probability q = p^{c\\lambda D}(1-p)^{\\lambda} = \\Theta((\\lambda D)^{-\\lambda}), then sets \\ell = O((\\lambda D)^{2\\lambda}). For one triplet the failure probability is exp(-\\Omega((\\lambda D)^{\\lambda})), and the union bound over n^{2\\lambda} triplets is claimed to give n^{-\\Omega(\\lambda)}. This requires (\\lambda D)^{\\lambda} = \\Omega(\\log n), which is false when D = O(1): a graph can have constant diameter and arbitrarily large n. For example, with \\lambda=1 and D=3, the probability that a unique bridge is absent from all sampled subgraphs is a constant independent of n, not n^{-1}. The randomized algorithm therefore needs a \\log n factor in \\ell, giving poly(D,\\log n) rounds, not poly(D) rounds as Theorem 1 states. The deterministic construction has the same gap. An FT-universal family (Def. 12) with b=1 must, for every ordered pair of distinct edges (e,f), contain a set S with e\\in S and f\\notin S (take A={e}, B={f}). Hence the membership signatures of all m edges are distinct, so the family has size at least \\log m. Lemma 17's bound ~O((4a)^{O(1)+2b}) inherits a polylog n factor from Claim 16's perfect-hash family, and the signature argument shows that factor is unavoidable for this type of family when D=O(1). Thus Theorem 2 also overclaims pure poly(D). The DHNS19 question is still answered if the results are restated as poly(D,\\log n), so the paper is repairable, but the central claim as written is stronger than the proof supports.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16335,"tokens_out":17595,"duration_ms":196968,"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":[{"comment":"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":"Section 2, Claim 9"},{"comment":"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":"Section 2.1, Lemma 17 and Theorem 2"},{"comment":"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.","section":"Section 2, paragraph after Theorem 1"}],"minor_comments":[{"comment":"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":"Section 3 / Figure 1"},{"comment":"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.","section":"Section 3 / Figure 1"},{"comment":"The citation '[Vad12, ?]' contains a stray '?' and should be completed.","section":"Fact 15"},{"comment":"The lemma states epsilon in [0,1], but the proof and Lemma 5 require epsilon in (0,1); please correct the range.","section":"Lemma 27"},{"comment":"The abstract contains the typo 'resolves one the open problems'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is likely salvageable: the central sampling and certificate arguments are sound, but Theorem 1 and Theorem 2 overclaim poly(D), and the necessary fixes (adding log n factors, correcting Lemma 17's bound and the deterministic round count) change the stated contributions. I recommend a major revision rather than rejection. The authors should also carefully re-derive Claim 21's iteration count and align the pseudocode with the text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis 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.\n\nThat 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.\n\nThe '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.\n\nThe 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.\n\nBottom 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.","headline":"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.","tokens_in":16968,"tokens_out":6052,"would_cite":true,"duration_ms":62148,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68W20","05C40","68R10","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["distributed minimum cut","CONGEST model","edge connectivity","connectivity certificates","fault-tolerant sampling","universal sets","low-congestion cycle covers","fault-tolerant spanners"],"falsifier":"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.","tokens_in":15738,"feed_emoji":"🕸️","tokens_out":14316,"duration_ms":143953,"temperature":0.7,"pith_summary":"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.","feed_headline":"Poly(D) rounds find exact min cuts in low-connectivity networks","feed_subtitle":"Constant-connectivity graphs were thought to need roughly D+√n rounds; fault-tolerant sampling makes the problem local.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the centralized low-congestion cycle-cover construction that Corollary 20 depends on to cover every short cycle by a near-short cycle.","marker":"[PY19a]"},{"why":"supplies the distributed (d,c)-cycle-cover algorithm used inside ApproxCycleCover for the round bound and congestion guarantee.","marker":"[PY19b]"},{"why":"provides deterministic neighborhood covers and spanner derandomization used in Lemma 22 and the deterministic certificate construction.","marker":"[GK18]"},{"why":"provides the ultra-sparse O(n)-edge spanner algorithm, the base spanner copied lambda times in Observation 26 for sparse certificates.","marker":"[Pet10]"},{"why":"provides the random edge-sampling theorem used in Lemma 27 to decompose a lambda-connected graph into subgraphs with connectivity Theta(log n/epsilon^2).","marker":"[Kar99]"},{"why":"provides the generic edge-fault-tolerant spanner transformation (Fact 24) that turns any spanner algorithm into an f-FT-spanner construction.","marker":"[CLPR10]"},{"why":"provides the vertex-fault-tolerant spanner meta-construction and the fault-tolerant sampling technique that the deterministic universal-set derandomization targets.","marker":"[DK11]"},{"why":"provides the almost pairwise independent hash families used in Claim 16 to build the perfect hash functions behind FT-universal sets.","marker":"[Vad12]"}],"fun_headline_variants":["Fault-tolerant sampling yields poly(D) min cut in constant-connectivity graphs","Min cut becomes local with fault-tolerant certificates","Poly(D) min cut for constant-connectivity graphs via fault-tolerant design","Resolving STOC'19 open problem: poly(D) min cut via fault tolerance","Local min cut in constant-connectivity graphs: fault-tolerant approach"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fault-tolerant sampling yields poly(D) min cut in constant-connectivity graphs","Min cut becomes local with fault-tolerant certificates","Poly(D) min cut for constant-connectivity graphs via fault-tolerant design","Resolving STOC'19 open problem: poly(D) min cut via fault tolerance","Local min cut in constant-connectivity graphs: fault-tolerant approach"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000727,"raw_usage":{"total_tokens":3332,"prompt_tokens":1098,"completion_tokens":2234,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":714,"completion_tokens_details":{"reasoning_tokens":2139}},"tokens_in":714,"tokens_out":2234,"duration_ms":16537,"temperature":1.0,"reasoning_tokens":2139,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:29:06.963835+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}