{"id":"f5f843de-1878-4181-9335-59019a1b48f5","arxiv_id":"2504.17955","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For the Marco Polo problem (binary radial probes), the paper gives algorithms using 2.53 to 6 times log-base-2 of n probes, a lower bound of 2.4 times log n, and an O(log k)-competitive strategy for finding all k targets.","lead":"This paper introduces a search problem where a searcher can only ask yes/no questions about whether a hidden target is within a certain radius, like calling Marco and hearing Polo. The authors design strategies that find one or many targets with bounded numbers of questions and bounded travel distance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound proof covers only a stricter memoryless model; the paper's own all-negative recursion and possible negative-information cell refinement are not analyzed, so the 2.40001 constant is not established for the stated algorithm class.","rationale":"I read the paper in good faith; the contribution is a new probe model and a family of shrinking-disk algorithms, and much of the upper-bound machinery is self-consistent. The most load-bearing issue is the lower-bound theorem, because the paper's headline comparison (2.53 upper vs 2.40001 lower) is only meaningful if the lower bound applies to the same class as Algorithms 1-8. The manuscript's own algorithms violate the memoryless assumption used in the proof (all-negative recursion), and the proof never rules out using negative information inside the successful probe to shrink to a smaller disk. This is an internal-consistency issue rather than a disagreement with consensus. The reader's weakest_assumption pointed at the perimeter-coverage assertion; I agree the lower-bound section is the soft spot, but I would sharpen it to the missing formal class definition and the recurrence branches. The TSP O(log k) claim is also overstated (the dn additive term is not absorbed), but it is separable and easier to fix; it is not the load-bearing point. Since the concern is addressable by formalizing the model and either repairing or narrowing the theorem, the conditional verdict stands.","tokens_in":14945,"tokens_out":24010,"duration_ms":274567,"concrete_test":"Take the exact recurrences including (a) the all-negative branch: if m probes fail, recurse to the minimal disk containing the complement; and (b) the positive branch: if probe i succeeds after i-1 failures, recurse to the minimal disk containing probe_i minus the union of the preceding probes. For up to m=20 probes per level, optimize over placements to minimize c = max over branches of (probes used)/(-log(shrink factor)). If any placement gives c < 2.40001, Theorem 1 fails for the class that includes the paper's own Algorithm 1; if the optimum stays above 2.40001, the proof can be repaired. A cheap first subset is to run this for the published Algorithm 1 and Algorithm 4 placements and compare the coefficient against the memoryless formula.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2's lower bound assumes a memoryless model: 'any algorithm must at least probe the perimeter', and the recurrence P(n)=k+P(ρ_k n) is derived by assuming the first success is on the k-th probe, so the new search area is the whole k-th probe disk. The constant 2.40001 then follows from covering the perimeter with disks of radii 2^{-k/c}. The paper never proves that this recurrence covers the class it calls 'progressive shrinking'. In particular, Algorithm 1 and the 'omission of the last probe' optimization progress on an all-negative outcome by recursing to the last unprobed region; the lower-bound argument does not model that branch. More generally, when probe i is the first positive probe, the feasible region is probe_i minus the union of probes 1..i-1, whose minimal enclosing disk can be substantially smaller than the probe disk. An algorithm that recurses to that smaller disk would need fewer probes than P(ρ_k n), possibly lowering the coefficient below 2.40001. The sum equation and chord-placement optimality are thus necessary but not sufficient; the missing step is a formal definition of the algorithm class and a recurrence that includes all-negative and negative-information branches. This is a proof gap, not a demonstrated falsehood: if the class is intended to be memoryless, the theorem statement should say so and exclude Algorithm 1's branch.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Marco Polo problem, a geometric localization problem in which a mobile search point issues binary 'yes/no' probes (radius-d disks) and must localize one or more stationary points of interest (POIs) within distance n of the origin. The authors propose a series of progressive-shrinking algorithms, from simple hexagonal tiling to computer-assisted 'darting' probe placements, with worst-case probe counts ranging from 5⌈logn⌉ down to 2.53⌈logn⌉. They also prove a lower bound of about 2.4⌈logn⌉ probes for 'progressive shrinking algorithms,' present a family of algorithms trading off probe count against the number of POI responses, and give a memoryless multi-POI extension whose traveled distance is O(log k)-competitive with the optimal TSP tour. The paper includes pseudocode, omitted proofs in an appendix, and large-scale simulations (40 million runs per algorithm).","tokens_in":15234,"tokens_out":7295,"duration_ms":70139,"significance":"If the central lower bound and the advertised upper-bound constants are correct, the paper makes a clean contribution: it defines a natural combinatorial geometric search problem, gives a nearly tight constant-factor characterization (2.4⌈logn⌉ versus 2.53⌈logn⌉), and provides several algorithm families with different trade-offs among probes, traveled distance, and POI responses. The multi-POI extension to an O(log k)-competitive TSP-style tour is also a useful result. Strengths of the manuscript include the breadth of algorithmic ideas, the use of computer-assisted placement with explicit numerical constants, the careful experiments (including Table 1 and Figures 13–15), and the transparent reporting of a discrepancy between theoretical worst-case bounds and observed finite-n performance in Observation 8. The paper is generally well written and the algorithms are described in enough detail to be reproducible.","major_comments":[{"comment":"The lower-bound argument rests on two unproven assertions: (i) that every progressive shrinking algorithm must probe the entire perimeter of the current search area at each level, and (ii) that after the first positive probe k, the residual uncertainty is exactly the full disk of radius ρ_k n. Neither is established. In particular, the algorithms themselves exploit the all-negative branch: the 'omission of the last probe' optimization recurses to the final unprobed region when all prior probes in a level are negative, and this branch is not modeled by the recurrence P(n)=k+P(ρ_k n). Moreover, when probe i is the first positive probe after i−1 negative responses, the feasible region is probe_i minus the union of the earlier probes, whose minimal enclosing disk can be substantially smaller than the probe disk. An algorithm that recurses to that smaller disk could use fewer probes than P(ρ_i n), potentially lowering the coefficient below 2.40001. The numerical equation Σ sin^{-1}(2^{-k/c}) = π is therefore necessary but not sufficient for the theorem as stated. Theorem 1 should either restrict its scope to a precisely defined memoryless algorithm class that provably excludes these branches, or the lower-bound recurrence must incorporate all-negative and negative-information branches.","section":"Section 2, 'A Lower Bound for Progressive Shrinking'"},{"comment":"The upper-bound constants in Theorem 1 and Figures 4, 6, and 7 (e.g., P(n) < 3.54⌈logn⌉, P(n) < 3.34⌈logn⌉, P(n) < 2.53⌈logn⌉) are stated as if they hold for every n, but Appendix F reports that progressive algorithms can exceed their theoretical worst-case bounds by an additive |probes|−2 term, and Table 1 shows empirical maxima above the stated bounds (e.g., Algorithm 3 max 4.25 versus bound 4.08; Algorithm 8 max 3.20 versus bound 2.53). The paper acknowledges this in Observation 8 and says the bound holds 'for sufficiently large n,' but that caveat is absent from the theorem statement. The claims in Section 2 and in the abstract should be phrased as asymptotic bounds with an explicit n0, or the theorem should state the corrected bound P*(n) = P(n) + |probes| − 2.","section":"Theorem 1 and Appendix F, Observation 8"},{"comment":"The probe-count bound in the multi-POI theorem uses the inequality Σ_{i=1}^{k−1} ⌈log e_i⌉ ≤ (k−1)⌈log e⌉, justified by 'Jensen's inequality' applied to the concave function log. This justification is invalid as written because the ceiling function is not concave, and Jensen's inequality applies to log, not to ⌈log⌉. The inequality may be true, but it requires a separate proof; for example, one would need to bound the gap introduced by the ceiling operation. As written, the proof of Theorem 5's probe bound is incomplete.","section":"Appendix C, proof of Theorem 6 (Theorem 5 in the main text)"}],"minor_comments":[{"comment":"The quoted phrase 'Macro' should be 'Marco' in the description of the children's game.","section":"Section 1, first paragraph"},{"comment":"The typesetting of Equation (4) is garbled; the binomial coefficient is not visually clear. Please reformat it for readability.","section":"Section 2, Equation (4)"},{"comment":"The formula r = (3L/2 − 1)s is stated for lattices with an even number of layers; the odd-layer case is dismissed in a parenthetical. Please give the explicit odd-layer formula or a short justification.","section":"Appendix C, Lemma 1 proof"},{"comment":"The table's 'Max' column is useful but should be annotated to indicate that for progressive algorithms the maximum observed value can exceed the displayed theoretical bound because of the last-layer effect discussed in Observation 8.","section":"Appendix F, Table 1"},{"comment":"The symbol P(n) is used both for the number of probes in the single-POI problem and for the probability-like notation elsewhere; consider a distinct symbol, e.g., P_1(n), to avoid confusion in Section 3.","section":"General notation"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a natural new problem and contains a substantial body of algorithmic work, but the two headline results—the 2.40001 lower bound and the 2.53 upper bound—are not yet fully established as stated. The lower-bound proof excludes branches that the paper's own algorithms use, and the upper bounds are acknowledged in Appendix F to be only asymptotic. If the authors can formalize the intended algorithm class and correct the asymptotic wording, and if they can supply a valid proof of the ceil-log inequality in Theorem 5, the paper would be a solid contribution. I recommend major revision rather than rejection because the gaps appear repairable and the algorithmic contributions are genuine."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper introduces a genuinely new query model and a solid family of algorithms for it. The binary radial probe—yes/no inside a disk, no direction or range—is a natural localization primitive, and the related-work appendix makes a credible case that it hasn't been studied before. The clean recurrence P(n)=k+P(ρ_k n), the progression from hexagonal tilings to chord-based shrinking to the computer-placed darting algorithms (down to 2.53⌈log n⌉ probes), and the response-limited variants are all real contributions. The authors are also unusually honest: Observation 8 admits that their own experiments show probe counts above the worst-case bounds for finite n, with an extra |probes|-2 term, and they flag that constants are asymptotic.\n\nThe soft spots are real but mostly addressable. The main one is the lower bound in Theorem 1. Section 2 asserts that any progressive shrinking algorithm must probe the perimeter, then derives the recurrence from 'first success on the kth probe' and takes the new search area to be the kth probe disk. That excludes branches the paper's own algorithms use: the 'omit the last probe' trick recurses on the all-negative region, and more generally, when probe i is first positive, the feasible region is probe_i minus the union of earlier probes, whose covering disk can be much smaller than the probe itself. An algorithm that recursed to that smaller disk could in principle beat 2.40001. The proof needs a formal definition of the algorithm class and a recurrence that covers all-negative and negative-information branches. This is a proof gap, not a demonstrated counterexample, but as written Theorem 1 does not cover the class it claims to bound.\n\nSecond, the abstract's O(log k)-competitive multi-target claim outruns the stated theorem. Theorem 5 gives Dtot≤dn+2dE with E