{"id":"0cc42e75-2068-46a7-8526-e3d574a038da","arxiv_id":"2411.13377","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For hypergraphs, the paper gives faster algorithms for k-weak maximal independent sets and a new (alpha,beta)-independent set variant, plus lower bounds in rank and degree.","lead":"This paper studies how fast distributed computers can find loosely independent sets in hypergraphs, where links can connect many nodes at once. It gives new algorithms and lower bounds for when such sets are cheap or expensive to compute.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's lower-bound reduction is invalid: the 'matching' M_i formed by choosing one incident hyperedge per 1-weak-MIS vertex need not be a matching, so the Ω(r) claim is not established.","rationale":"The reader's weakest_assumption also targets Theorem 7, but identifies a different defect (subhypergraphs leaving the stated family). My concern is more basic: even if the subhypergraphs stayed r-uniform and the family condition held, the constructed sets M_i need not be matchings because hyperedges incident to distinct MIS vertices can share a non-selected vertex. This invalidates the reduction from hypergraph maximal matching and leaves the Ω(r) lower bound unproved. I do not see a comparably decisive flaw in the main upper-bound construction: Theorem 23's defective-coloring approach appears plausible, though it has minor presentational issues (e.g., the partition sizes in Algorithm 4 are not always at most 5). Since the reader already marked the paper CONDITIONAL with high correctness risk, this concern reinforces rather than changes the verdict. The overall package may still be salvageable, but the current manuscript does not establish all of its advertised lower-bound claims.","tokens_in":16797,"tokens_out":14768,"duration_ms":176477,"concrete_test":"Run the reduction on the r=3 hypergraph with V={v1,v2,w,x1,x2} and edges e1={v1,w,x1}, e2={v2,w,x2}. The set S={v1,v2} is a 1-weak MIS. Apply Step 2: choosing e_{v1}=e1 and e_{v2}=e2 yields M_i containing intersecting edges, hence not a matching. More strongly, check every possible choice of one incident hyperedge per element of S; every choice still includes both e1 and e2, which intersect at w, so no matching can be produced. This demonstrates that the reduction cannot be repaired by a different tie-breaking rule on this valid instance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The Ω(r) lower bound in Theorem 7 rests on a reduction from hypergraph maximal matching. In Step 2 of the reduction, for each vertex v in the 1-weak MIS S_i of G_{i−1}, the proof selects an arbitrary incident hyperedge e_v and places it in M_i, then asserts that each M_i is a matching. This assertion is false: two selected vertices v,u ∈ S_i can choose hyperedges that intersect in a vertex outside S_i. For example, take r=3 with vertices {v1,v2,w,x1,x2} and edges e1={v1,w,x1}, e2={v2,w,x2}. The set S={v1,v2} is a 1-weak MIS, since each edge contains exactly one vertex of S and every outside vertex lies in an edge with an S-vertex. But the chosen hyperedges e1 and e2 share w, so {e1,e2} is not a matching. The subsequent claims that M=∪M_i is a matching and that it is a maximal matching to which Theorem 8 applies both require pairwise disjoint hyperedges. Because the proof gives no mechanism to avoid such intersections, and in the example no choice of one incident hyperedge per S-vertex can produce a matching, the reduction collapses. The manuscript also does not verify that the subhypergraphs G_{i−1} satisfy the family condition rΔ log(rΔ)=O(log n) after the vertex set shrinks, but the matching defect alone is decisive: the advertised Ω(r) lower bound is not established by the presented argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed algorithms for weak independent sets in hypergraphs in the LOCAL model. It introduces (α,β)-independent sets, gives an LLL-based existence/algorithmic formulation, a zero-round randomized construction, deterministic algorithms for (α,β)-IS and k-weak MIS, and three lower-bound theorems for 1-weak and k-weak MIS. The headline upper bound, Theorem 23, is a O(∆²(r−k) log r + ∆ log r log* r + log* n)-round deterministic algorithm for k-weak MIS, generalizing a result of Balliu et al. The headline lower bounds are Ω(r) (Theorem 7) and Ω(∆+log* n) (Theorems 9 and 10) for specific families of hypergraphs.","tokens_in":17045,"tokens_out":21236,"duration_ms":209830,"significance":"If correct, the upper bounds would be a meaningful step beyond the r−1-weak MIS algorithm of Balliu et al., and the (α,β)-IS framework is a natural generalization worth studying. The LLL formulation in Lemma 12 is a clean reduction, and Theorems 19 and 23 propose concrete algorithmic ideas with explicit round counts. The paper is not hiding fitted parameters: the main theorems are stated as explicit functions of ∆, r, n, and the proofs invoke standard external results (LLL, coloring, matching lower bounds). However, the advertised lower-bound result of Theorem 7 rests on an invalid construction, and the zero-round high-probability claim in Corollary 14 is not justified for the stated parameter range. These issues affect two of the paper's headline contributions, so the paper needs substantial revision before its claims can be relied upon.","major_comments":[{"comment":"The claim that each M_i is a matching is false. For two vertices v,u in the 1-weak MIS S_i, the arbitrarily chosen incident hyperedges e_v and e_u may intersect in a vertex outside S_i. Example with r=3: e1={v1,w,x1}, e2={v2,w,x2}, and S={v1,v2} is a 1-weak MIS, but no choice of one incident edge per S-vertex yields a matching because both edges necessarily contain w. Therefore the subsequent assertions that M = ∪ M_i is a matching and that M is a maximal matching to which Theorem 8 applies are unsupported. The reduction to maximal matching collapses, so Theorem 7's Ω(r) lower bound is not established by the presented argument. The proof also does not verify that each G_{i-1} still satisfies the family condition r∆ log(r∆)=O(log n) after vertices are deleted, but the matching defect is already decisive.","section":"Theorem 7, proof steps 2 and 3"},{"comment":"The zero-round high-probability claim is not justified by the stated condition. To conclude that the sampled set is an (α,β)-IS with probability 1−1/n^c one must union-bound over all n vertex events and all edge events. The per-event Chernoff bound in Eq. (3) gives a failure probability of at most 2 exp(−(β−α)²/(6(β+α))). With condition (4), this is at most 2/(e n^c), but the number of edges can be as large as n∆. The union bound then gives failure probability roughly (2/e) n^{1−c} ∆, which can exceed n^{−c} whenever ∆ is large (e.g., ∆=n). The condition omits ∆ (or the number of edges), which is why the proof fails. A corrected statement would need a bound such as (β−α)²/(β+α) ≥ 6c log n + 6 log ∆ + O(1), or an explicit bound on m in terms of n, ∆, and r.","section":"Corollary 14, Eq. (4)"},{"comment":"The statement of Lemma 17 is not well-formed: 'produces an m-weak independent set with expected size of m at least r/2k' mixes the weakness parameter m with the size of the produced set. As written it is not a theorem about the produced vertex set. Moreover, the analysis does not establish any k-weak independence guarantee: the procedure deletes one randomly chosen vertex per edge, but the surviving vertices in a given hyperedge can still be numerous. The argument that each part u_{e,i} retains at least one vertex gives only a lower bound on the intersection size per edge, not an upper bound of the form required for a k-weak (or m-weak) independent set. This section's claimed contribution ('0-round algorithm producing an m-weak independent set') is therefore not supported by the presented proof.","section":"Lemma 17 and Section 5"}],"minor_comments":[{"comment":"The reduction from a graph G on N vertices constructs a hypergraph G' on n = N·r/2 vertices. The Ω(∆+log* n) graph lower bound then transfers to Ω(∆+log* N) = Ω(∆+log*(2n/r)), not automatically Ω(∆+log* n) when r is close to n. The proof does not address this change in the vertex count; the theorem as stated requires additional argument or a restriction on r.","section":"Theorem 9, proof"},{"comment":"The proof states that inequality (5) is 'clearly true when |Vc|=1' (the case where A_e is kept as a single part). This is not correct: if A_e is a single part and has size larger than 1, proper coloring of H' gives |Vc∩e|=1, but the right-hand side ½(k−sat(e)) can be smaller than 1 (e.g. k−sat(e)=1). The argument can be repaired by using the algorithm's actual add condition |Vc∩e| ≤ k−sat(e), which holds because k−sat(e)≥1 for active, unsaturated edges, but the proof as written needs this correction.","section":"Theorem 23, proof, inequality (5)"},{"comment":"The instruction 'partition A_e into ⌊|A_e|/4⌋ parts of size at most 5' is not a well-defined partition (for example, |A_e|=6 would require two parts but ⌊6/4⌋=1). This is likely a typo for a partition into ⌈|A_e|/5⌉ parts or into parts of size at most 4; the proof's bound |Vc∩e| ≤ ¼|A_e| should be aligned with the actual part size.","section":"Algorithm 4, line 6"},{"comment":"There are small inconsistencies: the proof of Theorem 19 says 'O(∆r/α + log* n)' while the theorem and surrounding text use δ=β−α+1; the 'α-defective coloring' phrase should read 'δ-defective coloring'; and the claim that 'G′ is a regular graph' is not justified — it is only an arbitrary graph with bounded degree.","section":"Section 6.1 and Theorem 19 proof"},{"comment":"The conclusion states 'our lower bound Ω(∆+r+log* n)' for 1-weak MIS, but the paper only proves Ω(r) (Theorem 7, currently invalid) and Ω(∆+log* n) (Theorems 9–10) as separate bounds, not a single combined bound. The sentence should be rephrased to match the actual theorems.","section":"Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid upper-bound skeleton, especially the LLL formulation and the deterministic algorithms, but the lower-bound section contains a fundamental error that invalidates the advertised Ω(r) result. The zero-round claim also needs a corrected probabilistic condition. I would not recommend rejection because the upper bounds appear plausible and the fixes may be local, but the authors must either repair the matching reduction in Theorem 7 or significantly weaken the claim, and they must add the missing ∆-dependence to Corollary 14. The current draft also has several presentation issues (placeholder template fields, typos) that suggest it is an early version; a careful revision is needed before it is suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the paper introduces a genuinely useful parameterized relaxation and at least one algorithm that looks right, but the advertised Ω(r) lower bound is not proved. The proof of Theorem 7 claims that choosing one incident hyperedge per vertex of a 1-weak MIS yields a matching. That is false. Two selected vertices can choose hyperedges that intersect at an outside vertex; e.g., r=3 with edges {v1,w,x1} and {v2,w,x2} and S={v1,v2} is a 1-weak MIS, but the chosen edges share w. No choice of one edge per vertex avoids this. The later claims about M being a maximal matching collapse. Also, the reduction applies A to subhypergraphs G_i that are no longer r-uniform, and the family condition rΔ log(rΔ)=O(log n) is never rechecked after deletion. So the Ω(r) lower bound is unsubstantiated as written.\n\nWhat is genuinely new: the (α,β)-IS definition is a natural relaxation, and the LLL-based positive results (Lemma 12, Corollary 13) seem coherent. Theorem 23's O(Δ^2(r−k) log r + Δ log r log* r + log* n) algorithm for k-weak MIS is a plausible generalization of Balliu et al., though the proof is compressed. The zero-round Corollary 14 is plausible but needs the dependence on Δ and a proper union bound. Lemma 17 is not a well-formed claim and should be rewritten. The abstract also overclaims: Theorems 9 and 10 give Ω(Δ+log* n) for specific families, not a combined Ω(Δ+r+log* n) for the general problem.\n\nWho is this for: researchers in distributed symmetry breaking on hypergraphs; the (α,β)-IS definition and the defective-coloring machinery are the useful parts. It deserves referee time, but the referee should be skeptical of the lower-bound section and the abstract's claims. I would not cite the Ω(r) bound until it is fixed.","headline":"Novel (α,β)-IS framework and a plausible k-weak MIS algorithm, but the advertised Ω(r) lower bound rests on a false matching argument and needs major repair.","tokens_in":17638,"tokens_out":2857,"would_cite":false,"duration_ms":29731,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","05C65","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes LOCAL-round upper and lower bounds for weak maximal independent sets in hypergraphs, showing rank is an inherent lower-bound barrier while a gap-based relaxation admits zero-round randomized algorithms.","keywords":["distributed algorithms","LOCAL model","hypergraphs","weak maximal independent set","alpha-beta independent set","Lovasz Local Lemma","ruling sets","lower bounds"],"falsifier":"Run a candidate deterministic 1-weak MIS algorithm on the family of $r$-uniform hypergraphs with $r\\Delta\\log(r\\Delta)=O(\\log n)$; a single instance that terminates in $o(r)$ rounds refutes Theorem 7. To test the proof reduction itself, feed an algorithm known to work only on $r$-uniform inputs to the sequence $G_0,G_1,\\ldots$ generated by deleting vertices and edges; if the algorithm's output on some non-uniform $G_i$ is not a 1-weak MIS, the reduction's invocation of the algorithm on $G_{i-1}$ is invalid.","tokens_in":16538,"feed_emoji":"🕸️","tokens_out":9668,"duration_ms":96510,"temperature":0.7,"pith_summary":"The paper asks how many rounds of the LOCAL model a distributed network needs to elect an independent set when the network is a hypergraph, so one edge can span many vertices and a 'weak' independent set may take up to $k$ vertices from an edge. It proves that the weakest useful version, a 1-weak maximal independent set, cannot be found in $o(r)$ rounds on $r$-uniform hypergraphs of small degree, so the rank $r$ is an inherent barrier. On the algorithmic side, it gives a deterministic $k$-weak maximal independent set algorithm running in $O(\\Delta^2(r-k)\\log r + \\Delta \\log r \\log^* r + \\log^* n)$ rounds, and a family of $(\\alpha,\\beta)$-independent-set algorithms that run in $O(\\Delta r/(\\beta-\\alpha+1)+\\log^* n)$ rounds—or in zero rounds with high probability when the gap between $\\beta$ and $\\alpha$ is large. The $(\\alpha,\\beta)$ relaxation matters because it lets a network settle for a locally checkable approximation of maximality, which can be dramatically cheaper than true maximality.","feed_headline":"Rank forces Omega(r) rounds; relaxed sets need none","feed_subtitle":"A new analysis pins down when hypergraph independent sets are hard and when a single random choice suffices.","key_machinery":"The carrying object is the $(\\alpha,\\beta)$-independent set relaxation together with two accounting mechanisms. For the upper bounds, the algorithms split every edge into small parts, color the underlying graph of the split hypergraph, and activate color classes one by one; the saturation of an edge—the number of its vertices already in the set—and its phase control how many active vertices may still be added, so the $k$-weak MIS algorithm doubles the saturation of some incident edge in each phase and charges the $\\log r$ phases against $\\Delta$ incident edges. For the lower bounds, the key mechanism is reduction: a 1-weak MIS solver is invoked repeatedly, deleting matched hyperedges, to build a maximal matching whose $\\Omega(r\\Delta)$ lower bound transfers to $\\Omega(r)$; and blow-up constructions replace each graph vertex by $r/2$ (or $k$) copies, so that a 1-weak or $k$-weak MIS in the hypergraph projects back to an MIS in the original graph, transferring the graph $\\Omega(\\Delta+\\log^* n)$ bound. A third mechanism is a Lovász Local Lemma formulation—encoding the desired set as an outcome avoiding a family of bad events—with independent Bernoulli choices whose mean per edge is $(\\alpha+\\beta)/2$ and a Chernoff bound giving the required gap condition, plus a constructive LLL algorithm converting existence into a deterministic $O(\\log^2 n)$-round algorithm.","core_discovery":"The central claim is a complexity map for hypergraph independent sets. For $r$-uniform hypergraphs of maximum degree $\\Delta$, a $k$-weak maximal independent set—a set in which every edge has at most $k$ selected vertices and every unselected vertex sits in an edge with $k$ selected vertices—can be found in $O(\\Delta^2(r-k)\\log r + \\Delta \\log r \\log^* r + \\log^* n)$ LOCAL rounds. In the opposite direction, every deterministic 1-weak MIS algorithm needs $\\Omega(r)$ rounds on the family $r\\Delta\\log(r\\Delta)=O(\\log n)$, and $\\Omega(\\Delta+\\log^* n)$ rounds on even-rank hypergraphs; for odd $k$, a $k$-weak MIS on $2k$-uniform hypergraphs also needs $\\Omega(\\Delta+\\log^* n)$. The paper further introduces $(\\alpha,\\beta)$-independent sets, where the set is $\\beta$-weak and every vertex sits in an edge containing at least $\\alpha$ selected vertices, and shows these can be found deterministically in $O(\\Delta r/(\\beta-\\alpha+1)+\\log^* n)$ rounds, and with zero rounds of communication with high probability when $(\\beta-\\alpha)^2/(\\beta+\\alpha)\\ge 6c\\log n+6$.","pith_inferences":["A natural test of the algorithm's mechanism is to run the phase-doubling procedure on non-uniform hypergraphs, replacing $r$ by the maximum edge size; the saturation accounting is edge-local, so the proof structure should survive even if the round bound changes.","The zero-round threshold has the flavor of a phase transition: once the gap condition depends on $n$ rather than on $r\\Delta$, communication stops buying anything. Stretching the constant 6 down to the LLL threshold $ep(d+1)\\le 1$ would be the clean way to test how sharp that transition is.","For an application that only needs approximate maximality, the zero-round $(\\alpha,\\beta)$-IS is a ready-made primitive: when $(\\beta-\\alpha)^2/(\\beta+\\alpha)\\ge 6c\\log n+6$, each vertex decides independently and the network avoids all coordination cost.","The remaining gap for 1-weak MIS—an $O(r\\Delta+\\log^* n)$ upper bound against an $\\Omega(\\Delta+r+\\log^* n)$ lower bound—suggests the true complexity may be closer to $r\\Delta$; matching reductions alone likely cannot close it."],"forward_implications":["For $k$ close to $r$ and small $\\Delta$, the $O(\\Delta^2(r-k)\\log r + \\Delta\\log r\\log^* r + \\log^* n)$ algorithm beats the trivial $O(r\\Delta+\\log^* n)$ coloring method, so weak maximal independent sets become cheap at high weakness.","When the gap $\\beta-\\alpha$ is large enough that $(\\beta-\\alpha)^2/(\\beta+\\alpha)\\ge 6c\\log n+6$, an $(\\alpha,\\beta)$-independent set can be produced with zero communication, meaning the selected set is correct with high probability from purely local random choices.","The deterministic $(\\alpha,\\beta)$-IS algorithm yields $(2,k)$-ruling sets in $O(\\Delta(k + (2^{k-1}/3^{k-1})r)+\\log^* n)$ rounds, extending ruling-set constructions from graphs to hypergraphs.","The $\\Omega(r)$ lower bound for 1-weak MIS shows that for the weakest nontrivial requirement, no algorithm can escape a linear dependence on rank even when the degree is tiny.","For $k