{"id":"fb410c94-d6f8-4b30-8cd5-5f1515aa1437","arxiv_id":"2607.01216","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Presents O(n) query algorithms for hypergraph connected components and subquadratic bounds for k-connectivity in linear hypergraphs via cut oracles, bypassing exact reconstruction barriers.","lead":"The paper develops algorithms to find connected components in hypergraphs using cut queries, achieving O(n) expected queries for any weighted hypergraph and improved bounds for even-parity and linear cases. A smart generalist might read it to see how query models handle higher-order structures beyond simple graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly isolated the bypass mechanism as the key assumption. Because the high-level description is consistent with known graph-oracle techniques and states an explicit matching lower bound, the argument does not exhibit an obvious load-bearing gap on its own terms.","tokens_in":1772,"tokens_out":230,"duration_ms":34238,"concrete_test":"Verify that the expected number of CUT queries used to discover and coarsen one independent family is O(1) per vertex on average (by inspecting the pseudocode or recurrence in the connectivity section); if the per-family cost is O(n) or worse, the overall bound fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract describes a concrete algorithmic strategy—constructing independent families of vertex subpartitions with no shared hyperedges, then iteratively coarsening via existing weighted-graph connectivity oracles—that directly targets the identifiability barrier while preserving the O(n) query bound. No internal contradiction with the stated lower bound or with the parity-based reconstruction results is visible at the level of the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript claims that CUT oracles suffice to identify the connected components of any weighted hypergraph via a zero-error randomized algorithm using O(n) expected queries (matching the Ω(n) lower bound). The approach relies on constructing independent families of vertex subpartitions with no shared hyperedges and iteratively coarsening them via auxiliary weighted-graph connectivity oracles. For even-parity hypergraphs the paper further claims that a Möbius transform on the CUT function enables deterministic reconstruction, yielding \tilde{O}_r(kn) queries for k-connectivity certificates of r-bounded instances; for linear hypergraphs it claims a subquadratic \tilde{O}(kn^{1.5}) bound for the same task, improving on the general \tilde{O}(n^2) bound obtained from symmetric submodular minimization.","tokens_in":1817,"tokens_out":564,"duration_ms":33046,"significance":"If the algorithmic constructions and query analyses hold, the work supplies the first optimal (up to constants) connectivity algorithm for hypergraphs under CUT oracles and demonstrates that parity and linearity restrictions allow bypassing the fundamental identifiability barrier that prevents exact edge learning. The independent-family technique and the Möbius-based reconstruction constitute concrete, reusable primitives that could influence subsequent work on submodular query models and hypergraph sparsification.","major_comments":[{"comment":"§3 (the O(n) connectivity algorithm): the analysis establishing that the expected number of auxiliary-graph connectivity queries remains O(n) after each coarsening step must be checked against the precise definition of independent families; any hidden dependence on the number of hyperedges or on the weight distribution would invalidate the claimed bound.","section":"§3"},{"comment":"§4 (Möbius reconstruction for even-parity hypergraphs): the claim that the Möbius inversion yields a binary-search-style vertex identification procedure without additional rank or support assumptions needs an explicit statement of the support size of the recovered hyperedges; otherwise the \tilde{O}_r(kn) bound may degrade when r is not treated as a fixed constant.","section":"§4"}],"minor_comments":[{"comment":"The reference [Liao-Chakrabarty, 2024] is used as a black-box primitive; a one-sentence summary of the exact guarantee invoked (e.g., query complexity of the weighted-graph connectivity oracle) would improve readability.","section":null},{"comment":"Notation for the CUT oracle and for the independent-family partition should be introduced with a single displayed definition before the first algorithmic description.","section":null}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below with clarifications and revisions where needed.","responses":[{"response":"We have re-verified the analysis in §3 against the definition of independent families. These families are vertex subpartitions with no shared hyperedges by construction, so the auxiliary weighted graphs for connectivity queries have sizes linear in the current number of parts and their connectivity costs are independent of the total hyperedge count m and weight values. The expectation over random family selection yields O(current parts) auxiliary queries per coarsening round, summing to O(n) overall as the partition coarsens. No hidden dependence exists. We will add a clarifying remark in the revision.","revision_made":"partial","referee_comment":"[§3] §3 (the O(n) connectivity algorithm): the analysis establishing that the expected number of auxiliary-graph connectivity queries remains O(n) after each coarsening step must be checked against the precise definition of independent families; any hidden dependence on the number of hyperedges or on the weight distribution would invalidate the claimed bound."},{"response":"The Möbius inversion on the CUT function recovers hyperedge indicators exactly for even-parity instances. The binary-search vertex identification recovers hyperedges whose support size is at most r under the r-bounded assumption stated in the section. The \tilde{O}_r notation explicitly encodes the (polynomial) dependence on this fixed parameter r. We agree an explicit statement of the recovered support size (≤ r) will improve clarity and will include it in the revision.","revision_made":"yes","referee_comment":"[§4] §4 (Möbius reconstruction for even-parity hypergraphs): the claim that the Möbius inversion yields a binary-search-style vertex identification procedure without additional rank or support assumptions needs an explicit statement of the support size of the recovered hyperedges; otherwise the \tilde{O}_r(kn) bound may degrade when r is not treated as a fixed constant."}],"tokens_in":1502,"tokens_out":442,"duration_ms":39491,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main result is a zero-error randomized O(n)-query algorithm for connected components in weighted hypergraphs. It works by building independent families of vertex subpartitions with no shared hyperedges, then coarsening them with auxiliary weighted-graph connectivity oracles from the authors' prior work. This directly addresses the fact that distinct hypergraphs can have the same cut profile, so exact edge learning is impossible in general.\n\nThe parity angle is also new: for even-parity hypergraphs the cut function can be inverted with a Möbius transform to support binary-search style vertex identification, yielding deterministic tilde-O_r(kn) queries for k-connectivity certificates on r-bounded instances. Linear hypergraphs get a subquadratic tilde-O(kn^{1.5}) bound, beating the generic symmetric submodular minimization route.\n\nThese techniques look like genuine progress over the graph case and the cited submodular baseline. The lower-bound match and the explicit construction of independent families are the strongest parts.\n\nThe soft spot is that the abstract leaves the concrete construction and query accounting for the independent families implicit, so it is not yet clear whether the expectation stays linear in all cases or whether the Möbius step introduces hidden dependence on rank. No circularity is visible.\n\nThis is for people working on query models, cut oracles, or submodular optimization. A reader who cares about hypergraph connectivity or parity distinctions will get concrete new tools. It deserves peer review because the bounds are tight and the algorithmic ideas are specific enough to check.","headline":"The paper gives a clean O(n) connectivity algorithm for hypergraphs via independent families that sidesteps the identifiability barrier, plus parity-specific reconstruction with Möbius transforms.","tokens_in":2274,"tokens_out":375,"would_cite":false,"duration_ms":25982,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Hypergraph connected components can be identified with O(n) expected cut queries despite non-unique edge sets.","keywords":["hypergraph connectivity","cut oracles","query complexity","independent families","even-parity hypergraphs","linear hypergraphs","Möbius transform","k-connectivity"],"falsifier":"A weighted hypergraph on n vertices whose connected components cannot be recovered by any algorithm using o(n) cut queries in expectation.","tokens_in":2662,"feed_emoji":"","tokens_out":673,"duration_ms":18136,"temperature":0.7,"pith_summary":"The paper establishes that exact reconstruction of hyperedges is impossible in general because distinct hypergraphs can produce identical cut profiles, yet connectivity information remains recoverable. It introduces independent families of vertex subpartitions that share no hyperedges and uses them to iteratively coarsen the problem via standard weighted-graph connectivity routines. This yields a zero-error randomized algorithm matching the Omega(n) lower bound for any weighted hypergraph. For even-parity hypergraphs the cut function admits a Möbius inversion that supports deterministic k-connectivity certificates in near-linear queries when rank is bounded; linear hypergraphs obtain a subquadratic bound without parity restrictions.","feed_headline":"Hypergraph components found with O(n) cut queries","feed_subtitle":"Independent families bypass the identifiability barrier that blocks exact edge reconstruction.","key_machinery":"Independent families of vertex subpartitions that share no hyperedges, iteratively coarsened by weighted-graph connectivity routines.","core_discovery":"A zero-error randomized algorithm identifies the connected components of any weighted hypergraph using O(n) expected queries by introducing the notion of independent families of vertex subpartitions that do not share hyperedges and iteratively coarsening them using auxiliary weighted graph connectivity techniques. For even-parity hypergraphs a Möbius transform on the CUT function implements binary-search-style vertex identification, producing deterministic k-connectivity certificates for r-bounded even hypergraphs in tilde O_r(kn) queries. Linear hypergraphs admit a tilde O(kn^{1.5}) algorithm for the same task, improving on the general tilde O(n^2) bound from symmetric submodular minimizati","pith_inferences":["The technique may extend to other submodular cut oracles where exact reconstruction fails but partition information suffices.","Similar independent-family coarsening could reduce query costs for hypergraph partitioning or clustering tasks.","If the Möbius step generalizes beyond even parity, it might yield deterministic linear-query algorithms for broader hypergraph classes."],"forward_implications":["Weighted hypergraph connectivity is query-optimal and matches the graph case.","Exact edge reconstruction remains impossible, but connectivity bypasses the barrier.","Even-parity structure is fully recoverable for bounded-rank instances via Möbius inversion.","Linear hypergraphs admit strictly subquadratic k-connectivity certificates.","The same coarsening technique applies to any cut oracle that respects the independent-family property."],"fun_headline_variants":["O(n) cut queries identify hypergraph connected components","Even hypergraphs admit ~O(kn) k-connectivity queries","Linear hypergraphs admit ~O(kn^1.5) connectivity queries","Hypergraph connectivity via independent families and cut oracles"],"cache_read_input_tokens":64,"weakest_assumption_plain":"That families of vertex subpartitions without shared hyperedges can always be identified and coarsened until the connected components are isolated.","fun_headline_variants_meta":{"raw":{"variants":["O(n) cut queries identify hypergraph connected components","Even hypergraphs admit ~O(kn) k-connectivity queries","Linear hypergraphs admit ~O(kn^1.5) connectivity queries","Hypergraph connectivity via independent families and cut oracles"]},"model":"grok-4.3","cost_usd":0.009618,"raw_usage":{"total_tokens":4260,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":69,"cost_in_usd_ticks":96178000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3419,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":69,"duration_ms":46802,"temperature":1.0,"reasoning_tokens":3419,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-02T03:57:12.102588+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A weighted hypergraph on n vertices whose connected components cannot be recovered by any algorithm using o(n) cut queries in expectation.","supporting_citations":[],"review_version":1}