{"id":"1d621b35-2e0b-4474-a172-40a02b662d33","arxiv_id":"2606.06148","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A novel topological sphere covering theorem yields sharp list replicability bounds for VC classes and dimension-dependent bounds for large-margin halfspaces.","lead":"The paper proves a new sphere covering theorem from the Borsuk-Ulam result and uses it to derive tight bounds relating list size to accuracy in list replicability for learning algorithms. Smart generalists might read it to understand fundamental limits on making machine learning outputs reproducible without excessive computation.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Reduction encoding replicability as sphere covering by hemisphere-contained open sets may not be tight enough for claimed sharpness","rationale":"The reader's weakest_assumption correctly isolates the single modeling step whose validity is required for the topological theorem to deliver tight learning-theoretic bounds. The Borsuk-Ulam derivation itself is not the load-bearing point; the argument stands or falls on whether the sphere-covering formulation faithfully captures replicability. No other internal inconsistency is visible, and the paper supplies an independent topological result, so the reader's UNVERDICTED verdict is not altered.","tokens_in":1665,"tokens_out":384,"duration_ms":18715,"concrete_test":"Extract the precise definition of the open sets in the reduction (likely §3 or §4) and check whether every distribution-consistent replicable list of size k produces a covering satisfying the hemisphere condition, and conversely whether any covering with no (d+1)-wise intersection yields a distribution on which no list of size k is replicable; if either direction fails for half-spaces, the claimed optimality does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim obtains sharp list-size bounds for VC classes and half-spaces by reducing the replicability condition to a covering of S^d by open sets each contained in some open hemisphere, then invoking the new covering theorem (d+1 sets intersect). For the equality 'optimal list size = d' (when margin not too large) to hold, this modeling must be both sound (every replicable list induces such a covering) and complete (every such covering corresponds to a valid replicable list for some distribution). If the reduction introduces slack—e.g., the hemisphere condition is strictly weaker than the actual replicability constraint over all distributions—the derived upper bound on list size may be loose and the matching lower bound may fail to apply.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves a novel sphere covering theorem derived from Borsuk-Ulam: if the d-sphere is covered by open sets each contained in some open hemisphere, then d+1 of the sets must have nonempty common intersection. It applies the theorem to obtain sharp bounds relating list size to accuracy for replicable learning of VC classes, and shows that for large-margin halfspaces (margin not too large) the optimal list size equals the ambient dimension d, while providing a replicable algorithm achieving list size ceil(d/2)+1 when the margin is very large.","tokens_in":1837,"tokens_out":496,"duration_ms":25313,"significance":"If the central theorem and the modeling reduction both hold with no slack, the work would deliver the first tight (matching upper and lower) characterizations of list replicability for VC classes and halfspaces, a notable advance over prior non-sharp bounds in the area. The explicit derivation from Borsuk-Ulam and the algorithmic construction for the large-margin regime are clear strengths.","major_comments":[{"comment":"The modeling step that reduces replicability to a covering of the d-sphere by open sets each contained in an open hemisphere (the step underlying both the VC-class bound and the halfspace optimality claim) must be shown to be tight in both directions. If the hemisphere condition is strictly weaker than the replicability constraint that must hold for every distribution, then the derived upper bound on list size may be loose and the matching lower bound establishing optimality (list size = d) would not apply.","section":"Reduction from replicability to sphere covering (implicit in the passage from the learning problem to the topological st"},{"comment":"For the halfspace result claiming optimal list size exactly equals d when the margin is not too large, the manuscript must verify that the lower-bound construction (showing list size < d is impossible) survives the same geometric encoding; any gap between the covering condition and actual replicability over all distributions would falsify the equality.","section":"Application to large-margin halfspaces"}],"minor_comments":[{"comment":"The abstract states the VC-class bound only qualitatively; an explicit functional form (e.g., list size as a function of accuracy and VC-dimension) would improve readability.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading and constructive comments regarding the tightness of the modeling reduction. We address each major comment below and will revise the manuscript accordingly to make the equivalence explicit.","responses":[{"response":"We agree that an explicit demonstration of tightness in both directions is necessary to support the sharpness claims. The reduction is designed so that replicability over every distribution corresponds exactly to the open sets lying in open hemispheres (via the definition of list replicability and the geometry of the hypothesis space), with the converse also holding by construction of the covering. In the revision we will add a dedicated lemma and proof establishing the if-and-only-if equivalence between the replicability constraint and the hemisphere-containment condition.","revision_made":"yes","referee_comment":"[Reduction from replicability to sphere covering (implicit in the passage from the learning problem to the topological st] The modeling step that reduces replicability to a covering of the d-sphere by open sets each contained in an open hemisphere (the step underlying both the VC-class bound and the halfspace optimality claim) must be shown to be tight in both directions. If the hemisphere condition is strictly weaker than the replicability constraint that must hold for every distribution, then the derived upper bound on list size may be loose and the matching lower bound establishing optimality (list size = d) would not apply."},{"response":"We will revise the halfspace section to include an explicit check that the lower-bound construction (establishing that list size strictly less than d is impossible) is preserved under the same geometric encoding used for the sphere-covering argument. This verification will confirm that no modeling gap exists and that the claimed optimality (list size exactly equal to d) holds for margins that are not too large.","revision_made":"yes","referee_comment":"[Application to large-margin halfspaces] For the halfspace result claiming optimal list size exactly equals d when the margin is not too large, the manuscript must verify that the lower-bound construction (showing list size < d is impossible) survives the same geometric encoding; any gap between the covering condition and actual replicability over all distributions would falsify the equality."}],"tokens_in":1376,"tokens_out":469,"duration_ms":22048,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The key takeaway is that this paper supplies the first tight list replicability bounds for VC classes and for large-margin halfspaces, rather than asymptotic ones, by proving a new topological covering result.\n\nThe covering theorem says that any cover of the d-sphere by open sets each contained in an open hemisphere must have d+1 sets with nonempty intersection. It is derived directly from Borsuk-Ulam. The authors then apply it to obtain a sharp relation between list size and accuracy for VC classes, and they show that for halfspaces the optimal list size equals the ambient dimension when the margin is not too large, falling to ceil(d/2)+1 only for very large margins.\n\nThis is new. The covering statement is presented as novel and the exact constants do not reduce to earlier published results on replicability. The separation between the topological step and the learning applications is clean, and the work avoids parameter fitting or circular citations.\n\nThe main soft spot is the modeling reduction itself. Replicability is turned into a sphere covering with the hemisphere condition. For the claimed equalities to hold exactly, the reduction must be both sound and complete across all distributions. If the hemisphere condition is strictly weaker than the actual replicability constraint, the upper bound could be loose and the matching lower bound might not apply. The abstract states the results as sharp, so the paper must contain the argument that the encoding preserves optimality; that step is worth checking in detail.\n\nNo other load-bearing issues are visible. The topology rests on an external theorem and the claims are internally consistent.\n\nThis is for specialists in learning theory who want exact constants on reproducibility. A reader working on list replicability or geometric methods in algorithms will get concrete value. It deserves a serious referee to inspect the reduction and the covering proof.","headline":"New sphere covering theorem from Borsuk-Ulam yields the first tight list-size bounds for VC classes and margin halfspaces, but the reduction's exactness for those equalities needs verification.","tokens_in":2312,"tokens_out":447,"would_cite":false,"duration_ms":32598,"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":"A new sphere covering theorem from Borsuk-Ulam yields tight bounds on list size versus accuracy for replicable learning of VC classes.","keywords":["list replicability","VC dimension","sphere covering","Borsuk-Ulam theorem","half-spaces","reproducible learning","topological learning theory"],"falsifier":"An explicit cover of the d-sphere by open sets each inside some open hemisphere in which no d+1 sets intersect, or a concrete VC class and accuracy level where the minimal list size needed for replicable learning exceeds the bound derived from the theorem.","tokens_in":2592,"feed_emoji":"","tokens_out":737,"duration_ms":18579,"temperature":0.7,"pith_summary":"The paper proves that any cover of the d-sphere by open sets each contained in an open hemisphere requires d+1 sets to share a common point. It applies this topological fact to show sharp relationships between the list size needed for replicable learning and the accuracy parameter when the hypothesis class has finite VC dimension. The same approach gives exact optimal list sizes for large-margin half-spaces that depend on whether the margin is moderate or very large. A reader would care because list replicability formalizes reproducibility requirements, and knowing the minimal list size tells how many candidate outputs an algorithm must return to guarantee both accuracy and reproducibility.","feed_headline":"Sphere covering theorem sharpens replicability list bounds","feed_subtitle":"The topological result gives exact minimal list sizes needed for accurate, reproducible learning of VC classes and large-margin half-spaces.","key_machinery":"The novel sphere covering theorem stating that any cover of the d-sphere by open sets each contained in an open hemisphere must contain d+1 sets with a common intersection point.","core_discovery":"The central claim is a sphere covering theorem: if the d-sphere is covered by open sets each lying inside some open hemisphere, then some d+1 of the sets have nonempty intersection. This theorem is derived from the Borsuk-Ulam theorem. Using it, the paper establishes that for any VC class the minimal list size required to achieve replicable learning at accuracy epsilon is tightly characterized in terms of the VC dimension. For half-spaces with margin not too large the optimal list size equals the ambient dimension d; when the margin is taken very large an explicit replicable algorithm achieves the smaller list size of ceil(d/2)+1.","pith_inferences":["The same covering argument could be adapted to other learning problems that involve symmetric choice among hypotheses.","Practical replicable algorithms for linear classifiers might exploit the dimension-dependent list sizes shown for half-spaces.","The result suggests that topological methods can replace combinatorial arguments when deriving tight sample-complexity bounds for reproducibility constraints."],"forward_implications":["For any hypothesis class with finite VC dimension the minimal list size for replicable learning is a sharp function of accuracy and VC dimension.","For half-spaces whose margin is bounded away from the maximum possible value the smallest achievable list size equals the ambient dimension.","When the margin is taken sufficiently large a simple replicable algorithm exists whose list size is only ceil(d/2)+1.","The topological reduction supplies matching upper and lower bounds on list size for these families."],"fun_headline_variants":["Sphere covering theorem gives replicability list bounds","Novel sphere cover theorem for replicable learning","Replicability list size for halfspaces is d or d/2 +1","VC class replicability lists characterized by dimension"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The replicability requirement for learning can be modeled exactly as a covering of the d-sphere by open sets each contained in an open hemisphere.","fun_headline_variants_meta":{"raw":{"variants":["Sphere covering theorem gives replicability list bounds","Novel sphere cover theorem for replicable learning","Replicability list size for halfspaces is d or d/2 +1","VC class replicability lists characterized by dimension"]},"model":"grok-4.3","cost_usd":0.007817,"raw_usage":{"total_tokens":3569,"prompt_tokens":669,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":78174500,"prompt_tokens_details":{"text_tokens":669,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2839,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":669,"tokens_out":61,"duration_ms":21677,"temperature":1.0,"reasoning_tokens":2839,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T02:04:59.751558+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit cover of the d-sphere by open sets each inside some open hemisphere in which no d+1 sets intersect, or a concrete VC class and accuracy level where the minimal list size needed for replicable learning exceeds the bound derived from the theorem.","supporting_citations":[],"review_version":1}