{"id":"f69c453d-78a2-46b0-a3b8-813a53f7e8f5","arxiv_id":"2411.10107","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A fixed point of a d-dimensional monotone contraction can be found in O((c log(1/ε))^{ceil(d/3)}) queries, improving on previous bounds, and the problem lies in UEOPL.","lead":"This paper studies functions that are both monotone and contracting on a cube, and gives faster algorithms for finding their approximate fixed points. It also improves the best-known algorithm for approximating the value of Shapley stochastic games and places that problem in the complexity class UEOPL.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 84's proof that Up(f)∩B is non-empty misuses Lemma 80; the downward-closedness of D is unproven, so the almost-square critical box of Lemma 81 is unsupported and the O(log n) query bound is at risk.","rationale":"The reader's weakest-assumption analysis correctly identified Lemma 81 (existence of almost-square critical boxes) as the load-bearing step of the 3D algorithm, but did not pinpoint the invalid inference inside its proof. My stress-test goes further: Lemma 84, which supplies the Up(f)∩B point needed by Lemmas 86 and 87, rests on a misstatement of Lemma 80. Specifically, Lemma 80's strict upward direction requires y ≥ x with the i-th coordinate fixed, and says nothing about all y ≤ x. The paper uses it to assert downward closedness of D and then to claim that any x in Up(f) is above every point of B. The logical gap is concrete: from “no y′ < y is in Up(f)” one can only conclude that an Up(f) point is not strictly below y; it may still be incomparable with y. This invalidates the diagonal-projection step in Lemma 84. Since Lemmas 86, 87, and the final proof of Lemma 81 all consume the output of Lemma 84, the O(log n) query algorithm for 3DMAC is currently unproven at its core. I do not claim the theorem is false; the reductions for UEOPL containment (Sections 4–5) and the decomposition theorem (Section 7) appear carefully argued and are independent of this step. But the headline algorithmic result, the O(log(1/ε)) query bound in dimension 3, is conditioned on repairing or bypassing this gap. The proposed brute-force test can settle the issue for small grids: either a counterexample refutes Lemma 84, or the search provides some corroboration that the gap is fixable. Given the complexity of Section 8 and the specific flaw found, the appropriate verdict remains conditional: the paper should not be accepted until Lemma 84's inference is corrected and verified, ideally with the computational check proposed here.","tokens_in":1288,"tokens_out":1199,"duration_ms":83684,"concrete_test":"Brute-force enumerate all functions f : {1,...,n}^3 → {1,...,n}^3 for n = 4 and n = 5 that satisfy: unit displacements, monotonicity, 1-Lipschitzness, the boundary-inward preprocessing of Lemmas 53 and 70, and the 1DUniqueDMAC condition. For each function and each 2D slice s, compute the path B from Definition 82 and check two assertions: (a) D = {x : f3(x) > x3} is downward closed; (b) Up(f)∩s ≠ ∅ implies Up(f)∩B ≠ ∅. If either assertion is violated for any instance, Lemma 84 is false and the proof of Lemma 81 fails. If no counterexample appears up to n=5, repeat the search on the restricted class of functions produced by the interpolation and shifting construction of Section 7.2, since those are the instances the algorithm actually receives.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The keystone of the 3D algorithm is Lemma 81 (Section 8.3): if Up(f)∩s is non-empty, an almost-square critical box exists. Its proof depends on Lemmas 84–87, which locate Up(f) points on the boundary path B and compare their height functions. The specific weakness is in Lemma 84. The text asserts: “Lemma 80 tells us that if f3(x) > x3 and if y ≤ x then f3(y) > y3. So the set D is downward closed.” That is a misreading of Lemma 80. The lemma's strict upward case says: “If fi(x) > xi, and y is a point such that y ≥ x and yi = xi, we have fi(y) > yi.” It requires y ≥ x, not y ≤ x, and it requires the i-th coordinate to be unchanged. It does not license the claimed downward-closedness of D for all y ≤ x. Consequently, the following observation in Lemma 84, “x ≥ y for all points y ∈ B,” is not established. The proof only shows that no y′ < y can lie in Up(f), which gives “not(x < y)”, not the coordinatewise inequality x ≥ y in a partial order. Since the rest of Lemma 84, and then Lemmas 86–87, rely on moving from an arbitrary Up(f) point diagonally down along the path B, the existence of Up(f)∩B is left unproven. If Lemma 84 fails, the intermediate-value argument in Lemma 87 has no starting point, so Lemma 81 has no proof. Lemma 81 is what justifies the grid-search refinement in Sections 8.4–8.6: the algorithm needs an almost-square critical box to know that a constant-size grid either hits the up-set or localizes a small region containing it. Without Lemma 81, the claimed constant-factor area reduction per iteration, and hence the O(log n) query bound, collapses. The reductions in Sections 4–7 may be sound, but the central algorithmic claim depends on this unverified step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies functions f : [0,1]^d → [0,1]^d that are both monotone and contracting in the ℓ∞ norm. It defines the discrete problem DMAC and claims three main results: (1) DMAC and hence MonotoneContraction lie in UEOPL via a promise-preserving reduction to OPDC; (2) a three-dimensional DMAC instance can be solved with O(log n) queries, where n = Ω(1/ε), with each step polynomial time; and (3) a decomposition theorem converts any LFP-solver in dimensions d1 and d2 into one in dimension d1+d2, yielding an O((c log(1/ε))^{⌈d/3⌉})-query algorithm in dimension d. The results are applied to Shapley stochastic games. The most intricate part is Section 8, which gives the three-dimensional algorithm; Section 8.3 develops the almost-square critical box lemma (Lemma 81) on which the query-count argument rests. In the version under review, the proof of Lemma 81 is cut off and the preceding Lemma 84 relies on a misstatement of Lemma 80. The earlier sections (4–7) are detailed and, as far as I checked, internally coherent.","tokens_in":60996,"tokens_out":9053,"duration_ms":83203,"significance":"If the Section 8.3 concerns are resolved, the results would be a substantial improvement over the previous state of the art: they place monotone-contraction fixed-point finding in UEOPL (not previously known), reduce the query complexity from O(log^{⌈d/2⌉}(1/ε)) to O((c log(1/ε))^{⌈d/3⌉}), and the per-step polynomial runtime addresses the drawback of Chen et al.'s O(d² log(1/ε))-query algorithm. The paper is genuinely strong in several places: the contiguity proof for fixed points (Lemma 17), the polynomial-time least-fixed-point verification (Lemma 19), the reduction to OPDC with violation handling (Section 5.3), the 1DUniqueDMAC reduction and surface characterization (Section 6), and the decomposition theorem (Section 7.1) are all carefully presented with detailed arguments. The main doubt sits at the keystone of the algorithm: Section 8.3's claim that an almost-square critical box always exists. Because the query complexity of the grid-search subroutines depends on that lemma, the algorithmic main claims are conditional on a repair of the issues I identify.","major_comments":[{"comment":"The proof of Lemma 84 states that 'Lemma 80 tells us that if f3(x) > x3 and if y ≤ x then f3(y) > y3' and uses this to conclude that the set D of points with f3(x) > x3 is downward closed. This inverts the hypotheses of Lemma 80: the third bullet of Lemma 80 requires y ≥ x and yi = xi, not y ≤ x. Consequently, the conclusion 'x ≥ y for all points y ∈ B' is not established, and the construction of a point in Up(f) ∩ B fails. Since Lemma 84 is the starting point of the intermediate-value argument in Lemma 87, and Lemma 87 is used in the proof of Lemma 81, the existence of an almost-square critical box—used in Sections 8.4–8.6 to justify the constant-size grid search—is not proven. This is load-bearing for the O(log n) query claim.","section":"8.3, Lemma 84"},{"comment":"In the version provided, the proof of Lemma 81 ends mid-sentence with '≤ Height1(xi+1) + 1 − (Hei', cutting off in the middle of the case analysis for xi+1 = xi + e1 and before the case xi+1 = xi − e2 is presented. The reader cannot check the claimed reductions of Height1/Height2 or the resulting construction of the almost-square box. Combined with the flaw in Lemma 84, the statement 'If Up(f) ∩ s is non-empty then there exists a critical box with |h−w| ≤ 1' is unsupported in this version. Please provide the full proof or repair the argument.","section":"8.3, Lemma 81 proof"}],"minor_comments":[{"comment":"The text says 'the reduction is correct for the case when x3 = 1 and x1 > n', but the lemma requires x1 > 1; the variable x1 ranges only up to n in G′. This appears to be a typo that could mislead readers.","section":"6.3, proof of Lemma 71"},{"comment":"Figures 16 and 17 are referenced in the interpolation description, but the figures are not included in the text I reviewed; the claim that the surfaces match on cube boundaries and that the gradients are at most one cannot be fully checked in their absence.","section":"7.2, Step 1"},{"comment":"The word 'analagously' should be 'analogously'.","section":"Footnote 5"}],"recommendation":"major_revision","confidential_remarks":"The truncation in Section 8.3 may be an artifact of the review format; if the arXiv version contains the full proof of Lemma 81, the authors should be asked to point to the specific lines. Even so, the misreading of Lemma 80 in the proof of Lemma 84 is present in the text I reviewed and must be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely new and important paper, but the main algorithmic claim is currently unsupported. The 3D O(log(1/ε)) query bound rests on Lemma 81, which rests on Lemma 84, and Lemma 84's proof misuses Lemma 80.\n\nWhat's new and good: the paper launches the study of monotone contractions as a computational problem, defines DMAC, gives a promise-preserving reduction to OPDC to put the problem in UEOPL, and proves a decomposition theorem that turns any 3D solver into a d-dimensional solver with exponent ceil(d/3). Sections 4–7 read carefully and the reductions are detailed. The Shapley-game consequences would be a real advance.\n\nThe soft spot is in Section 8.3. Lemma 84 asserts that if Up(f) ∩ s is non-empty then Up(f) ∩ B is non-empty, and the proof claims that 'Lemma 80 tells us that if f3(x) > x3 and y ≤ x then f3(y) > y3.' That's backwards. Lemma 80's strict upward case requires y ≥ x with yi = xi, not y ≤ x. So the set D = {x : f3(x) > x3} is upward closed, not downward closed, and the subsequent claim that x ≥ y for every y in B is not established. The stress-test note is right about this. Without Lemma 84, the intermediate-value argument in Lemma 87 has no starting point, so Lemma 81 (almost-square critical box) is unproven. The grid-search refinement in Sections 8.4–8.6 needs Lemma 81 to guarantee the constant-factor area reduction; without it the O(log n) query count collapses.\n\nTo be fair, the conclusion of Lemma 84 may be salvageable — the geometry of upward-closed sets suggests that every point in the up-set should have some point of B below it — but the current text doesn't supply that argument, and the later sections depend on it. The rest of the 3D algorithm is too complex to fully verify from the truncated text; the terminal phase and invariants also need scrutiny.\n\nRecommendation: this deserves a serious referee. The paper should not be desk-rejected. The UEOPL containment and decomposition theorem are solid enough to be valuable on their own, and the flaw in Lemma 84 is localized. Send it to review with the expectation that Section 8.3 be rewritten and the proof of Lemma 81 made complete; acceptance should be conditional on that.","headline":"Strong, novel results for monotone contractions, but the 3D algorithm's keystone Lemma 84 misuses Lemma 80, so the O(log(1/ε)) query bound is not yet proven.","tokens_in":61724,"tokens_out":9120,"would_cite":true,"duration_ms":81831,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A monotone contraction in three dimensions admits an O(log(1/ε))-query algorithm for ε-approximate fixed points, and the problem lies in UEOPL.","keywords":["monotone contractions","fixed point approximation","query complexity","UEOPL","DMAC","Shapley stochastic games","Tarski fixed point theorem","decomposition theorem"],"falsifier":"Enumerate all monotone non-expansive displacement fields on a small grid, say $5\\times 5\\times 5$, with inward boundary behavior and test Lemma 81: a single slice whose up-set is non-empty but whose every critical box satisfies $\\lvert h-w\\rvert\\ge 2$ would falsify the 3D query bound. Alternatively, implement the algorithm on a family of monotone contractions built by rotating the displacement field by 90 degrees and check whether the carried-over bounds shrink by a constant fraction at each slice; a failure would show the carried-over bound lemma is false.","tokens_in":60427,"feed_emoji":"🎲","tokens_out":8425,"duration_ms":85706,"temperature":0.7,"pith_summary":"The paper studies functions $f:[0,1]^d\\to[0,1]^d$ that are both monotone and contracting in the $\\ell_\\infty$ norm, and asks how many evaluations suffice to locate an $\\varepsilon$-approximate fixed point. It claims that three-dimensional monotone contractions can be solved with $O(\\log(1/\\varepsilon))$ queries, with each step running in polynomial time, and that this improves the known polynomial-time bounds for functions that are only monotone or only contracting. The central vehicle is a discrete grid problem, DMAC, whose fixed points or violations map back to the continuous function; DMAC is shown to lie in UEOPL, and a decomposition theorem lifts the 3D algorithm to $O((c\\log(1/\\varepsilon))^{\\lceil d/3\\rceil})$ queries in $d$ dimensions. Since Shapley stochastic games reduce to monotone contractions, the same results give a faster algorithm for approximating Shapley game values and place that problem in UEOPL.","feed_headline":"O(log 1/ε) queries find fixed points of 3D monotone contractions","feed_subtitle":"Method extends to d dimensions and speeds up approximate Shapley game values.","key_machinery":"The load-bearing objects are the discrete monotone approximate contraction (DMAC) instance, its one-dimensional surfaces, and the critical boxes used to bound the up-set in a two-dimensional slice. A surface is the unique height at which a fixed one-dimensional slice is stationary; in a violation-free instance every surface is monotone and has gradient at most one, which lets bounds be translated diagonally from one slice to the next. A critical box is a rectangle inside the up-set whose right, top, and lower-left exits all move strictly downward, so the box together with its left, bottom, and diagonal lobes contains the whole up-set; the almost-square lemma says a critical box with $\\lvert h-w\\rvert\\le 1$ exists whenever the up-set is non-empty. The UEOPL containment is carried by a promise-preserving reduction to One Permutation Discrete Contraction (OPDC), using the least-fixed-point verification sequence and mapping every OPDC violation back to a monotonicity or non-expansion violation of DMAC.","core_discovery":"On the paper's own terms, the discovery is that combining monotonicity with contraction makes fixed-point search structurally easier than either condition alone. The paper defines DMAC, a discrete function on a grid with unit displacements that can output a fixed point, a monotonicity violation, or a non-expansion violation, reduces monotone contractions to it, and proves DMAC lies in UEOPL by selecting the least fixed point as the unique solution. The least fixed point is efficiently verifiable because a non-least fixed point is always approached by another fixed point one unit away, so a short verification sequence certifies it. The algorithmic core is a 3D DMAC solver that maintains a bound on the up-set made of a critical box and three lobes, shrinks the bound by a constant fraction per query using grid searches, cone arguments, and bounds carried between slices, and finishes with a terminal phase on a slice that contains a fixed point. The decomposition theorem then multiplies this 3D solver to higher dimensions.","pith_inferences":["The paper does not claim a matching lower bound; if the 3D base case is optimal, the decomposition theorem makes $\\lceil d/3\\rceil$ the bottleneck, so any faster general algorithm would need a better 3D fixed-point search rather than a better composition.","A continuous analogue of the almost-square critical box lemma would remove the discretization slack in the reduction from monotone contractions to DMAC; whether the exact-square version holds in $\\mathbb{R}^3$ is not addressed by the paper.","The promise-preserving reduction means the algorithm could serve as a violation detector for purported monotone contractions: if the produced OPDC instance reports a violation, the original function provably violates monotonicity or non-expansion, even though the paper states this only in complexity-theoretic terms."],"forward_implications":["A 3D monotone contraction admits an $\\varepsilon$-approximate fixed point with $O(\\log(1/\\varepsilon))$ function evaluations, each evaluation processed in polynomial time.","For $d$ dimensions the same construction needs $O((c\\log(1/\\varepsilon))^{\\lceil d/3\\rceil})$ evaluations and runs in polynomial time per step, improving the previous $O((c\\log(1/\\varepsilon))^{\\lceil d/2\\rceil+1})$ polynomial-time bound for monotone functions.","Approximating the value of a Shapley stochastic game with $d$ states lies in UEOPL and can be done in time $O((c\\log(1/\\varepsilon))^{\\lceil d/3\\rceil}\\cdot \\mathrm{poly}(|G|))$.","For functions that are only contracting and not monotone, the best polynomial-time algorithms need $\\log^d(1/\\varepsilon)$ evaluations, so monotonicity removes nearly all of the dimension dependence in the exponent.","The least fixed point of a DMAC instance can be verified in polynomial time, in contrast to monotone functions alone, where the same verification is NP-hard even in one-dimensional instances."],"supporting_citations":[{"why":"It supplies Tarski's fixed point theorem, which guarantees the least fixed point used as the unique solution in the UEOPL reduction.","marker":"[28]"},{"why":"It defines OPDC and proves it UEOPL-complete; the paper's UEOPL containment is a promise-preserving reduction from DMAC to OPDC.","marker":"[14]"},{"why":"It shows that Shapley and simple stochastic games reduce to monotone contractions, carrying the paper's algorithmic and complexity results over to games.","marker":"[9]"},{"why":"It provides the decomposition theorem and 3D algorithm for monotone functions that this paper adapts, compares against, and improves.","marker":"[15]"},{"why":"It gives the $O(d^2\\log(1/\\varepsilon))$-query algorithm for contractions whose running time is not polynomial, the main contrast for the new polynomial-time monotone-contraction result.","marker":"[5]"},{"why":"It provides the best previous polynomial-time monotone-function algorithm via Tarski*, which is the baseline the new exponent beats.","marker":"[3]"},{"why":"It establishes the prior polynomial-time query complexity for contractions in arbitrary dimension, which the monotone-contraction results improve.","marker":"[23, 24]"}],"fun_headline_variants":["Monotone contractions: fixed points in O(log 1/ε) queries","3D monotone contractions: fixed points in log queries","Monotone + contraction: fixed point search in UEOPL","Faster Shapley game values via monotone contraction fixed points"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The constant-factor shrinking step works only if every nonempty up-set in a two-dimensional slice contains a critical box whose height and width differ by at most one (Lemma 81); if that fails, the per-query progress guarantee and the $O(\\log(1/\\varepsilon))$ query count collapse.","fun_headline_variants_meta":{"raw":{"variants":["Monotone contractions: fixed points in O(log 1/ε) queries","3D monotone contractions: fixed points in log queries","Monotone + contraction: fixed point search in UEOPL","Faster Shapley game values via monotone contraction fixed points"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000796,"raw_usage":{"total_tokens":3525,"prompt_tokens":985,"completion_tokens":2540,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":2476}},"tokens_in":601,"tokens_out":2540,"duration_ms":20984,"temperature":1.0,"reasoning_tokens":2476,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:59:13.418504+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all monotone non-expansive displacement fields on a small grid, say $5\\times 5\\times 5$, with inward boundary behavior and test Lemma 81: a single slice whose up-set is non-empty but whose every critical box satisfies $\\lvert h-w\\rvert\\ge 2$ would falsify the 3D query bound. Alternatively, implement the algorithm on a family of monotone contractions built by rotating the displacement field by 90 degrees and check whether the carried-over bounds shrink by a constant fraction at each slice; a failure would show the carried-over bound lemma is false.","supporting_citations":[{"cited_title":"A lattice-theoretical fixpoint theorem and its applications","cited_arxiv_id":null,"evidence_quote":"It supplies Tarski's fixed point theorem, which guarantees the least fixed point used as the unique solution in the UEOPL reduction."},{"cited_title":"Unique end of potential line","cited_arxiv_id":null,"evidence_quote":"It defines OPDC and proves it UEOPL-complete; the paper's UEOPL containment is a promise-preserving reduction from DMAC to OPDC."},{"cited_title":"Papadimitriou, A viad Rubi nstein, and Mihalis Yannakakis","cited_arxiv_id":null,"evidence_quote":"It shows that Shapley and simple stochastic games reduce to monotone contractions, carrying the paper's algorithmic and complexity results over to games."},{"cited_title":"A f aster algorithm for finding Tarski fixed points","cited_arxiv_id":null,"evidence_quote":"It provides the decomposition theorem and 3D algorithm for monotone functions that this paper adapts, compares against, and improves."},{"cited_title":"Computing a fix ed point of contraction maps in polynomial queries","cited_arxiv_id":null,"evidence_quote":"It gives the $O(d^2\\log(1/\\varepsilon))$-query algorithm for contractions whose running time is not polynomial, the main contrast for the new polynomial-time monotone-contraction result."},{"cited_title":"Improved upper bounds for finding Tar ski fixed points","cited_arxiv_id":null,"evidence_quote":"It provides the best previous polynomial-time monotone-function algorithm via Tarski*, which is the baseline the new exponent beats."}],"review_version":1}