{"id":"ac489290-1b41-4700-85cc-9cd0645e7882","arxiv_id":"2607.06069","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Under Gap-ETH, the n^{O(1/ε^{d-1})}-time shifting PTAS is optimal for maximum independent set, minimum dominating set, maximum induced forest, maximum induced matching, and minimum piercing set on unit ball graphs in every constant dimension d≥2.","lead":"The paper proves that the classic shifting-based PTAS running time n^{O(1/ε^{d-1})} is optimal under Gap-ETH for several geometric problems on unit ball graphs in every constant dimension d≥2, resolving an open question that was previously settled only for d=2. A smart generalist reads this to learn which geometric approximation algorithms cannot be improved, closing the gap between known upper and lower bounds for problems like maximum independent set and minimum piercing on","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The gap-preservation chain and gadget constructions hold up under scrutiny; the reader's ACCEPT verdict is appropriate.","rationale":"The reader correctly identified the gap-preservation chain (particularly Claim 7 and the charging arguments) as the weakest assumption. I verified this concern does not land: the bound in Claim 7 is tight, the parameter setting ε = δ·s·c_d/n^{1/(d-1)} with s = Ω(log^{1/(d-1)} n) correctly preserves the gap, and the running-time calculation yields 2^{O(γ'n)} as claimed. Each subsequent reduction step (Proposition 8, Theorems 9-10) preserves the gap up to a constant factor depending only on d, which is absorbed into the final constant γ. The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching are intricate but the geometric claims are verified by the perturbation analysis with ρ = 1/(400Λ^{d+2}). The black-box use of [5] is standard. The paper makes a substantial contribution resolving Question 1 affirmatively under Gap-ETH, and the ACCEPT verdict with HIGH confidence is appropriate.","tokens_in":39491,"tokens_out":14722,"duration_ms":729474,"concrete_test":"Construct a small 2D Maximum Induced Forest instance from a TilingCSP instance with Λ=2, two variables, and one binary equality constraint. Verify numerically that: (1) the intersection graph has the claimed clique/cyclic-ordering structure (Claims 15-16), (2) the global forest F is a tree, (3) the maximum induced forest size equals Γ = (g+2τ)|V|+12|E| when the CSP is satisfiable, and (4) introducing a constraint violation reduces the optimum by the predicted factor. This would validate the most intricate new gadget construction end-to-end.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I traced the full reduction chain and verified gap preservation at each step. In Theorem 6, Claim 7's bound of 6κ affected clauses per violated constraint is correct: each violated constraint touches at most 2 small cubes, each intersecting at most κ = 6d·s^{d-1} wires, each wire mapping to a literal in at most 3 clauses, giving 2·κ·3 = 6κ. The resulting gap ε = δ·s·c_d/n^{1/(d-1)} with s = Ω(log^{1/(d-1)} n) makes the running-time calculation yield 2^{O(γ'n)}, contradicting Gap-ETH for small γ'. The charging arguments in Proposition 8 (|C'| ≤ c_d|C|, gap preserved up to constant factor) and Theorem 9 (similar) are sound. For the new Maximum Induced Forest gadget (Theorem 14), I verified the key geometric claims: Claim 15's intersection pattern follows from Δ² = (1+(r'-r)ρ)² + O(Λ²dρ²) with ρ = 1/(400Λ^{d+2}), giving Δ² ≥ 1 when r ≤ r' and Δ² < 1 when r > r'. The cycle-creation argument in Claim 18 (two intersecting consecutive clique balls form a cycle through the global forest F) is correct: the path in F between forest balls t_j and t_{j+1} does not pass through clique balls, so the 4-cycle clique_j → t_j → … → t_{j+1} → clique_{j+1} → clique_j is indeed a cycle. The error analysis (Claim 21: t ≤ 2ℓ, each partial gadget incident to ≤ 2d+1 constraints) is tight. The black-box use of [5] for Minimum Piercing Set (Theorem 30) relies on a standard locality property that is natural for geometric constructions. I found no load-bearing concern that undermines the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper establishes that the shifting technique of Hochbaum and Maass yields optimal PTAS running times (of the form n^{O(1/ε^{d-1})}) for several geometric problems on unit ball graphs in R^d, under Gap-ETH, for every constant dimension d ≥ 2. The framework proceeds by constructing a gap-preserving reduction chain from Max-(3,3)-SAT through GeometricCSP, ProjectionCSP, ≤-CSP, and TilingCSP (Theorem 1), using the Cube Wiring Theorem of De Berg et al. and reduction steps from Marx–Sidiropoulos. The authors then apply this framework to Maximum Independent Set, Minimum Dominating Set, Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set (Theorem 2), providing matching upper bounds via shifting for the latter three. The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching are the main technical contributions beyond the framework itself.","tokens_in":39833,"tokens_out":1487,"duration_ms":545133,"significance":"The paper resolves a natural and explicitly stated open question (Question 1) about the optimality of shifting-based PTASes in dimensions d ≥ 3. The gap-preserving reduction chain from Gap-ETH to TilingCSP/≤-CSP with the n^{Ω(1/ε^{d-1})} lower bound is the central contribution and appears sound. The new gadget for Maximum Induced Forest (Theorem 14), with its global forest structure, private balls, and cycle-creation argument, is a non-trivial adaptation of Marx's independent-set gadget and is likely of independent interest. The matching upper bounds for Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set via shifting and separator-based exact subroutines round out the contribution. The black-box use of the Blank et al. k-center gadgetry for Minimum Piercing Set is appropriate.","major_comments":[{"comment":"§5.2, Theorem 14, Claim 15 (p. 18): The proof of Claim 15 establishes the cyclic ordering property for consecutive clique positions on the *same side* of Q_v, where the directional vector d is shared. However, at corner positions (where d_j and d'_{j+1} are perpendicular), the distance calculation changes because consecutive positions lie on different sides of the square. The proof states the corner case uses perturbation ι(s)ρ(d_j + d'_{j+1}), but the distance analysis for whether balls at corner-adjacent positions intersect or are disjoint is not explicitly verified. Since the cyclic ordering argument requires the property to hold at *every* consecutive pair around the entire cycle (including all four corners), this gap should be addressed with an explicit calculation or a reference to where it is verified.","section":null},{"comment":"§5.2, Theorem 14, d ≥ 3 construction (pp. 21–24): The transition from the d = 2 construction to d ≥ 3 via the Hamiltonian cycle on the cross-polytope is described at a high level, but several geometric details that are carefully specified for d = 2 are omitted for d ≥ 3. Specifically: (a) the exact placement of private and forest balls at corner positions along the Hamiltonian cycle (where perpendicular transitions occur) is stated to be feasible due to 'enough room' but without explicit coordinates or distance bounds; (b) the connector chain geometry between gadgets on non-axis-aligned facets is not fully specified. Since the cyclic ordering property (Claim 15) and the connector consistency (Claim 16) are load-bearing for the reduction's correctness, the authors should either provide the missing geometric verification for d ≥ 3 or clearly state that the d = 2 arguments extend verbatim (","section":null}],"minor_comments":[{"comment":"§3, Theorem 6 proof (p. 10): The text references 'Theorem 7' in two places ('by Theorem 7') where it should reference Claim 7. This is a cross-reference error.","section":null},{"comment":"§4.1, Proposition 8 (p. 12): The direction of the inequality |C| ≤ c_d|C'| in the proof appears inconsistent with the charging argument. The text charges each constraint of C' to a constraint of C, with each constraint of C charged at most O(3^d) times, which should give |C'| ≤ c_d|C|. The subsequent argument uses ε/c_d as the fraction, which is consistent with |C'| ≤ c_d|C|, but the stated inequality |C| ≤ c_d|C'| seems reversed.","section":null},{"comment":"§5.2, Figure 8 (p. 19): The coordinates listed for t_1 involve a square root expression that is not fully simplified. A cleaner expression or a note that this is the unique point satisfying the tangency condition would improve readability.","section":null},{"comment":"§5.5, Theorem 30 (p. 31): The footnote about scaling the point set by 1/(2r_0) to make balls have unit diameter is slightly confusing since the main text already defines unit balls as having diameter 1. Clarifying that the scaling is applied to the output of [5] to match this convention would help.","section":null},{"comment":"§6.1, Theorem 36 (p. 35): The alternative approach using P-flattened treewidth is mentioned in a single sentence. A brief citation to the specific theorem in [12] that yields the n^{O(ℓ^{d-1})} bound would make this more verifiable.","section":null},{"comment":"Throughout: The notation switches between 'unit ball' (open ball of diameter 1) and 'unit disk' (in the d = 2 case). Using 'unit ball in R^2' consistently, or explicitly stating that 'unit disk' means 'unit ball in R^2', would improve consistency.","section":null},{"comment":"§1.1, Figure 2 (p. 5): The reduction chain diagram shows 'Max-≤-CSP' and 'Max-TilingCSP' but the text sometimes refers to these without the 'Max-' prefix. Consistency would help.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong contribution that resolves a well-known open question. The reduction framework is carefully built and the new gadgets are interesting. The two major comments are about completeness of geometric verification at corner positions and in higher dimensions — these are fixable by adding explicit calculations or clarifying that the arguments extend, and do not appear to indicate any fundamental error. The reader's report and stress-test note both confirm the soundness of the core reduction chain and the gap-preservation arguments. I recommend minor revision with the expectation that the geometric details at corners and for d ≥ 3 are made explicit."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for the careful reading and the constructive feedback. The referee has identified two genuine gaps in the geometric verification of our gadget construction for Maximum Induced Forest (Theorem 14). We address both below and will revise the manuscript accordingly.","responses":[{"response":"The referee is correct that the proof of Claim 15 as written only handles the case where consecutive positions p_j and p_{j+1} lie on the same side of Q_v and share a common directional vector d. The corner case—where p_j is the last position on one side and p_{j+1} is the first position on the perpendicular side—requires a separate distance calculation that we omitted. We will add this calculation explicitly in the revised manuscript. The key observation is that at a corner, the two consecutive positions are at unit ℓ_1-distance (they differ in two coordinates, each by 1/2 in the d=2 construction with unit spacing along the boundary), and the perturbation at the corner position is ι(s)ρ(d_j + d'_{j+1}), which has components along both directional vectors. Writing out the squared distance between B_j(v,s) and B_{j+1}(v,s') at a corner, the dominant term is the ℓ_1-distance between p_j and p_{j+1} (which is 1), and the perturbation contributes a correction of order (r'-r)ρ in the relevant direction plus O(Λ^d ρ) in the perpendicular direction. The same inequality chain as in the same-side case applies: if r ≤ r', the distance is at least 1 (disjoint), and if r > r', the distance is strictly less than 1 (intersecting), since 10Λ^{2d}ρ^2 ≪ ρ. We will include this calculation in full in the revision.","revision_made":"yes","referee_comment":"§5.2, Theorem 14, Claim 15 (p. 18): The proof of Claim 15 establishes the cyclic ordering property for consecutive clique positions on the same side of Q_v, where the directional vector d is shared. However, at corner positions (where d_j and d'_{j+1} are perpendicular), the distance calculation changes because consecutive positions lie on different sides of the square. The proof states the corner case uses perturbation ι(s)ρ(d_j + d'_{j+1}), but the distance analysis for whether balls at corner-adjacent positions intersect or are disjoint is not explicitly verified. Since the cyclic ordering argument requires the property to hold at every consecutive pair around the entire cycle (including all four corners), this gap should be addressed with an explicit calculation or a reference to where it is verified."},{"response":"The referee raises a valid point. For d ≥ 3, we relied on informal geometric intuition ('enough room') without providing the explicit verification that the referee rightly requests. We will address both sub-points in the revision. For (a), the key difference from d = 2 is that in d ≥ 3, the box Q_v has side length 30 (rather than 11), and the corner positions along the Hamiltonian cycle on the cross-polytope involve transitions between facets whose normals are orthogonal. At each corner position, the private ball is placed in the direction of the outward facet normal, and the forest ball is placed in the direction of the inward normal. Because d ≥ 3 provides an additional dimension orthogonal to both directional vectors d_j and d'_{j+1}, the private and forest balls at corner positions can be displaced into this extra dimension, ensuring they do not create unwanted intersections with balls at non-adjacent positions. We will provide explicit coordinates for the private and forest ball placements at corner positions, analogous to those given in Figure 8 for d = 2, and verify the required intersection properties by direct distance calculation. For (b), the connector chains in d ≥ 3 are always axis-aligned (they connect gadgets along grid edges in direction e_i), so the connector geometry is identical to the d = 2 case—the entry and exit ports on facet F_i (with normal e_i) face the corresponding ports on facet F_{i+d} (with normal -e_i) of the adjacent gadget, and the intermediate clique positions are placed along the e_i direction exactly as in d = 2. We will state this explicitly in the revision and note that Claims 15 and 16 hold verbatim for d ≥ 3 because the connector geometry is unchanged and the corner-position calculation for the cyclic ordering property follows by","revision_made":"no","referee_comment":"§5.2, Theorem 14, d ≥ 3 construction (pp. 21–24): The transition from the d = 2 construction to d ≥ 3 via the Hamiltonian cycle on the cross-polytope is described at a high level, but several geometric details that are carefully specified for d = 2 are omitted for d ≥ 3. Specifically: (a) the exact placement of private and forest balls at corner positions along the Hamiltonian cycle (where perpendicular transitions occur) is stated to be feasible due to 'enough room' but without explicit coordinates or distance bounds; (b) the connector chain geometry between gadgets on non-axis-aligned facets is not fully specified. Since the cyclic ordering property (Claim 15) and the connector consistency (Claim 16) are load-bearing for the reduction's correctness, the authors should either provide the missing geometric verification for d ≥ 3 or clearly state that the d = 2 arguments extend verbatim."}],"tokens_in":39210,"tokens_out":1557,"duration_ms":96412,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper proves that shifting-based PTASes with running time n^{O(1/ε^{d-1})} are Gap-ETH-optimal for all constant d≥2, resolving the natural extension of Marx's FOCS'07 result from 2D to arbitrary fixed dimension. The framework covers five problems: Maximum Independent Set, Minimum Dominating Set, Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set on unit ball graphs. The main technical contribution is a gap-preserving reduction from Max-(3,3)-SAT to GeometricCSP using the Cube Wiring Theorem of De Berg et al., which replaces the Matrix Tiling approach that Marx showed does not extend to 3D. The subsequent steps in the chain (GeometricCSP → ProjectionCSP → ≤-CSP/TilingCSP → target problems) largely reuse constructions from Marx-Sidiropoulos, but the authors verify that each step is approximation-preserving with explicit charging arguments. The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching are nontrivial adaptations — the forest gadget in particular requires a global forest structure and private balls to enforce the clique and disjointness properties that come for free in the independent set setting. The matching upper bounds via shifting are provided for the three problems where they were not already known. The reduction chain is carefully done. I traced the gap preservation: Claim 7's bound of 6κ affected clauses per violated constraint checks out (2 cubes × κ wires × 3 clauses), and the parameter choice s = Ω(log^{1/(d-1)} n) makes the running time calculation yield 2^{O(γ'n)}, contradicting Gap-ETH. The charging arguments in Proposition 8 and Theorem 9 are sound — only constant-factor losses at each step, which is all that's needed. The black-box use of Blank et al. for Minimum Piercing Set relies on a locality property that is standard for this type of geometric construction. The soft spots are minor. The d=2 case uses edge-disjoint wiring rather than vertex-disjoint, which is handled correctly but slightly less cleanly than the d≥3 case. The Maximum Induced Forest gadget is intricate — the private ball and forest ball placement involves careful geometric bookkeeping — but the key claims (Claims 15, 17, 18, 21) hold up. The error analysis is tight where it needs to be and loose where it can afford to be. This paper is for researchers in geometric approximation and parameterized complexity. It deserves a serious referee — the main result is a clean resolution of a well-known open question, and the framework is reusable for future lower bounds in higher-dimensional geometric settings.","headline":"Shifting PTAS lower bounds extended to all constant dimensions — solid framework, worth a serious referee","tokens_in":40397,"tokens_out":614,"would_cite":true,"duration_ms":84786,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Shifting proved optimal for geometric approximation in every dimension","keywords":[],"falsifier":"A PTAS for Maximum Independent Set (or any of the other four problems) on unit ball graphs in R^d for some fixed d >= 3 running in time n^{o(1/epsilon^{d-1})} would contradict Gap-ETH if the paper's reduction chain is correct. Conversely, a flaw in the gap-preservation argument at any stage of the reduction chain would weaken or invalidate the lower bound.","tokens_in":39762,"feed_emoji":"📐","tokens_out":1351,"duration_ms":269795,"temperature":0.7,"pith_summary":"The paper proves that the classical shifting technique of Hochbaum and Maass produces the fastest possible polynomial-time approximation schemes for a range of geometric problems on unit ball graphs in every fixed dimension d >= 2, assuming Gap-ETH. Previously, this optimality was known only for d=2 (due to Marx, FOCS 2007). The authors develop a lower-bound framework built on a chain of gap-preserving reductions: starting from Max-(3,3)-SAT, they embed the formula's incidence graph into a d-dimensional grid using the Cube Wiring Theorem, construct a geometric CSP instance whose variables encode wire values in small grid cubes, and then reduce through Projection CSP, TilingCSP, and <=-CSP to reach target problems. The framework yields matching upper and lower bounds of n^{O(1/epsilon^{d-1})} for Maximum Independent Set, Minimum Dominating Set, Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set on unit ball graphs in R^d. The key structural insight is that the wire-cube intersection locality ensures that a constant fraction of violated clauses in the original formula propagates proportionally to a constant fraction of violated CSP constraints, preserving the gap through every reduction step.","feed_headline":"Shifting proved optimal for geometric approximation in every dimension","feed_subtitle":"Under Gap-ETH, the n^{1/ε^{d-1}} running time of shifting-based PTASes is tight for five problems on unit ball graphs in all constant","key_machinery":"The reduction chain proceeds through five stages: (1) Max-(3,3)-SAT to Max-GeometricCSP via Cube Wiring embedding with wire-cube encoding; (2) Max-GeometricCSP to Max-ProjectionCSP via the Marx-Sidiropoulos construction with a charging scheme showing each constraint is charged at most O(3^d) times; (3) Max-ProjectionCSP to Max-<=-CSP via cycle gadgets with 12 variables per original variable; (4) Max-ProjectionCSP to Max-TilingCSP by replacing inequality constraints with equality constraints; (5) Max-TilingCSP or Max-<=-CSP to each target geometric problem via problem-specific gadget constructions. The shifting upper bound uses a randomly shifted grid of side length O(1/epsilon), where each d","core_discovery":"The central discovery is a gap-preserving reduction chain from Max-(3,3)-SAT to geometric constraint satisfaction problems on d-dimensional grids, where the Cube Wiring Theorem embeds the formula incidence graph using vertex-disjoint wires, and each grid cube's variable encodes the Boolean values of the at most kappa = 6d * s^{d-1} wires passing through it. This locality structure ensures that each violated CSP constraint corrupts at most 6kappa clauses, so the gap propagates with the parameter choice epsilon = delta * s * c_d / n^{1/(d-1)} and s = Omega(log^{1/(d-1)} n). The resulting hardness for Max-TilingCSP and Max-<=-CSP (Theorem 1) then transfers to five geometric problems via problem","pith_inferences":["The framework likely extends to other problems on intersection graphs of fat objects (e.g., unit squares, unit cubes, pseudo-disks) in fixed dimension, since the shifting upper bound and the reduction gadgets depend primarily on the intersection geometry of congruent fat objects.","If Gap-ETH is weakened to ETH, the lower bound degrades from n^{Omega(1/epsilon^{d-1})} to 2^{Omega(1/epsilon^{d-1})} * poly(n), matching the EPTAS lower bound regime; the tightness of the PTAS lower bound specifically requires the gap amplification that Gap-ETH provides.","The parameter s = Omega(log^{1/(d-1)} n) in the reduction suggests a natural trade-off between the wire density per cube and the formula size; this could connect to separator-based exact algorithms where the O(1/epsilon^{d-1}) separator size arises from the same dimensional geometry."],"forward_implications":["Any new PTAS for geometric problems on unit ball graphs in R^d with running time n^{O(1/epsilon^{d-1})} is now conditionally optimal under Gap-ETH, closing the gap between upper and lower bounds for the five problems studied.","The framework can be applied to other geometric problems on unit ball or unit cube intersection graphs by constructing gap-preserving reductions from Max-TilingCSP or Max-<=-CSP, following the pattern established by the five applications.","The distinction between EPTAS lower bounds (2^{Omega(1/epsilon^{d-1})} form) and PTAS lower bounds (n^{Omega(1/epsilon^{d-1})} form) is now bridged for these geometric problems, showing that the n^{1/epsilon^{d-1}} dependence is inherent and not an artifact of the shifting technique.","The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching, which use private balls to enforce clique exclusivity and a global forest to enforce disjointness of consecutive selections, provide reusable templates for proving hardness of other induced substructure problems."],"fun_headline_variants":["Shifting PTAS running times are optimal under Gap-ETH","Gap-ETH proves shifting is optimal for geometric PTASes","Optimality of shifting PTASes shown for all constant dimensions","Framework proves shifting PTASes optimal under Gap-ETH","Shifting algorithms optimal for geometric approximation under Gap-ETH"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The gap-preserving property of the reduction from Max-(3,3)-SAT to Max-GeometricCSP relies on the claim that each violated CSP constraint causes at most 6kappa violated clauses in the original formula, which depends on the wire-cube intersection structure: each small cube intersects at most kappa = 6d * s^{d-1} wires, and each wire corresponds to a literal appearing in at most 3 clauses. If the gap amplification is not tight enough at any step in the reduction chain, the n^{1","fun_headline_variants_meta":{"raw":{"variants":["Shifting PTAS running times are optimal under Gap-ETH","Gap-ETH proves shifting is optimal for geometric PTASes","Optimality of shifting PTASes shown for all constant dimensions","Framework proves shifting PTASes optimal under Gap-ETH","Shifting algorithms optimal for geometric approximation under Gap-ETH","Hardness framework proves shifting PTASes optimal under Gap-ETH","Geometric approximation: shifting PTASes are optimal under Gap-ETH","Shifting is optimal for geometric PTASes in any constant dimension"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1263,"prompt_tokens":557,"completion_tokens":706,"prompt_tokens_details":null},"tokens_in":557,"tokens_out":706,"duration_ms":32292,"temperature":1.0,"reasoning_tokens":602,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T17:23:57.175004+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A PTAS for Maximum Independent Set (or any of the other four problems) on unit ball graphs in R^d for some fixed d >= 3 running in time n^{o(1/epsilon^{d-1})} would contradict Gap-ETH if the paper's reduction chain is correct. Conversely, a flaw in the gap-preservation argument at any stage of the reduction chain would weaken or invalidate the lower bound.","supporting_citations":[],"review_version":1}