Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Monotone Contractions

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A monotone contraction in three dimensions admits an O(log(1/ε))-query algorithm for ε-approximate fixed points, and the problem lies in UEOPL.

desk verdict 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. read the letter →

arxiv 2411.10107 v2 pith:BUZRCHFY submitted 2024-11-15 cs.CC

Eleni Batziou , John Fearnley , Spencer Gordon , Ruta Mehta , Rahul Savani This is my paper · ORCID
classification cs.CC
keywords monotonecontractionsfixedpointapproximationquerycomplexityUEOPLDMACShapleystochasticgamesTarskitheoremdecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [8.3, Lemma 84] 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.
  2. [8.3, Lemma 81 proof] 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.
minor comments (3)
  1. [6.3, proof of Lemma 71] 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.
  2. [7.2, Step 1] 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.
  3. [Footnote 5] The word 'analagously' should be 'analogously'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: results are derived against external OPDC/UEOPL benchmarks; self-citations supply independent prior theorems.

full rationale

The paper's central claims (UEOPL containment, the O(log(1/ε)) 3D query bound, and the decomposition theorem) are derived from the definitions of monotone contractions and the discrete DMAC problem, not from the conclusions they are meant to establish. The reduction from MonotoneContraction to DMAC defines f from g by clamping displacements, and each solution type of the DMAC instance is mapped back to the corresponding solution of MonotoneContraction by explicit inequalities (Lemmas 6-9); this is a standard reduction, not a definitional equivalence between the target and the algorithm's output. The UEOPL containment is obtained by a reduction to OPDC, whose UEOPL-completeness is cited from prior work [14] by overlapping authors; that prior theorem is an independent, parameter-free result about a different problem and is not fed by the present paper's fitted values or assumptions, so it is real evidence rather than circularity. Similarly, Lemma 67 is cited from [15] as a standard monotone-function interpolation lemma, and the decomposition theorem is proved directly for LFP-solving algorithms. No parameter is fitted and then renamed as a prediction, and no 'uniqueness' choice is forced by a self-citation chain. The only concerns raised about Lemma 84 are potential mathematical gaps in the proof of an almost-square critical box; even if valid, such a flaw would be a correctness issue, not a circularity. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper relies on standard fixed-point theorems, the prior UEOPL-completeness of OPDC, and the known reduction from Shapley games to monotone contractions. No free parameters are fitted; the constant c in the query bounds is a universal constant from the algorithm. The interpolation and surface constructions are internal proof devices, not independent entities.

assumptions (6)
  • standard math Tarski's (Knaster-Tarski) fixed point theorem: every order-preserving map on a complete lattice has a least fixed point.
    Used throughout to define the least fixed point as the unique solution and to prove hereditariness (Theorems 13, 26).
  • standard math Banach fixed point theorem: a contraction on a complete metric space has a unique fixed point.
    Used in Section 1 to justify studying approximate fixed points of the unique exact fixed point of a monotone contraction.
  • domain assumption OPDC is UEOPL-complete (Fearnley, Gordon, Mehta, Savani 2019).
    The UEOPL containment is shown by a promise-preserving reduction to OPDC (Theorem 34). This external completeness result is cited, not re-proved.
  • domain assumption Shapley stochastic games reduce to monotone contractions (Etessami et al. 2008).
    The paper's game-theoretic applications depend on this reduction (Section 1), which is cited from [9] and not reproduced.
  • domain assumption Monotone functions satisfy a sandwich fixed-point lemma (Fearnley et al., Lemma 3.2 of [15]).
    Used in Lemma 68 to map the unique fixed point of the transformed instance back to the least fixed point of f; cited from prior work.
  • domain assumption DMAC instances can be assumed to have unit-length displacements (Lemma 11) and are represented by a polynomial-time Turing machine.
    Definitional input model used to bound query cost and to make surfaces well-defined.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monotone Contractions." pith.science (2026). https://pith.science/paper/BUZRCHFY

@misc{pith2026241110107,
  author       = {Pith},
  title        = {Pith review of: Monotone Contractions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BUZRCHFY}},
  note         = {Machine review of arXiv:2411.10107}
}
abstract

We study functions $f : [0, 1]^d \rightarrow [0, 1]^d$ that are both monotone and contracting, and we consider the problem of finding an $\varepsilon$-approximate fixed point of $f$. We show that the problem lies in the complexity class UEOPL. We give an algorithm that finds an $\varepsilon$-approximate fixed point of a three-dimensional monotone contraction using $O(\log (1/\varepsilon))$ queries to $f$. We also give a decomposition theorem that allows us to use this result to obtain an algorithm that finds an $\varepsilon$-approximate fixed point of a $d$-dimensional monotone contraction using $O((c \cdot \log (1/\varepsilon))^{\lceil d / 3 \rceil})$ queries to $f$ for some constant $c$. Moreover, each step of both of our algorithms takes time that is polynomial in the representation of $f$. These results are strictly better than the best-known results for functions that are only monotone, or only contracting. All of our results also apply to Shapley stochastic games, which are known to be reducible to the monotone contraction problem. Thus we put Shapley games in UEOPL, and we give a faster algorithm for approximating the value of a Shapley game.

Figures

Figures reproduced from arXiv: 2411.10107 by the authors.

Figure 1
Figure 1. Surfaces in a two-dimensional DMAC instance. Surfaces. Every one-dimensional slice of a 1DUniqueDMAC has a unique one-dimensional fixed point, and we think of these fixed points as a surface that spans the instance [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. A reduction to ensure that a two-dimensional insta [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Carrying over information from one inner binary se [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (39 more)
Figure 4
Figure 4. Figure 4: The structure of Up(f) in a two-dimensional slice. The structure of the up-set in a two-dimensional slice can be seen in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: A CB-config, and the corresponding region that is ru [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: An example in which Up(f) ∩ si lies in a lobe. However, we cannot proceed as before by refining the central square of this bound using a grid search [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Handling left lobes. Here we describe the procedure for a left lobe with width w and height h. The procedure for a bottom lobe is symmetric, and can be obtained by exchanging dimensions 1 and 2. The procedure for a diagonal lobe follows essentially the same approach, b…
Figure 8
Figure 8. Figure 8: The shape of the regions that we consider. [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Cases consituting contraction violations. [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]
Figure 10
Figure 10. Figure 10: An illustration of the region B(y, k − 1) ∩ B(x, k − 1) ∩ L(y, x) from Lemma 17 when y, x are at equal distance along all dimensions. Red points correspond to the boundary of the intersection. y x L(y, x) B(y, k − 1) B(x, k − 1) [PITH_FULL_IMAGE:figures/full_fig_p022…
Figure 11
Figure 11. Figure 11: An illustration of the region B(y, k − 1) ∩ B(x, k − 1) ∩ L(y, x) from Lemma 17. Red points are on the boundary of B(y, k − 1) ∩ B(x, k − 1), blue points are on the boundary of L(y, x) and points that are both blue and red are on the boundary of both. 22 [PITH_FULL_I…
Figure 12
Figure 12. Figure 12: A verification sequence for x, where (v i := VSeq(x)i) k i=0. The black arrows are the witnesses to each of the verification sequence points not being fixed, and the gray arrows are the directions of the displacements that must exist at every point on the cube that ar…
Figure 13
Figure 13. Figure 13: Distance between LFPs of neighboring slices. The [PITH_FULL_IMAGE:figures/full_fig_p027_13.png]
Figure 14
Figure 14. Figure 14: An illustration of Lemma 25. Proof. By assumption fi(y) 6= yi . If fi(y) > yi , we would have a violation of monotonicity, since, by assumption fi(x) = xi and y < x. Thus, we have fi(y) < yi (shown as the arrow in [PITH_FULL_IMAGE:figures/full_fig_p027_14.png]
Figure 15
Figure 15. Figure 15: A verification sequence in (a) and its projection i [PITH_FULL_IMAGE:figures/full_fig_p030_15.png]
Figure 16
Figure 16. Figure 16: The possible configurations of a surface intersec [PITH_FULL_IMAGE:figures/full_fig_p042_16.png]
Figure 17
Figure 17. Figure 17: Interpolation scheme based on the configuration o [PITH_FULL_IMAGE:figures/full_fig_p043_17.png]
Figure 18
Figure 18. Figure 18: A DBox(x, y, l). We also define a DBox, which is diagonal region with flattened ends, as shown in [PITH_FULL_IMAGE:figures/full_fig_p048_18.png]
Figure 19
Figure 19. Figure 19: A critical box. Throughout this section we consider a two-dimensional slice s of a three-dimensional instance. With￾out loss of generality we suppose that dimensions 1 and 2 are the dimensions used in the slice, and dimension 3 is the dimension that is not used in the…
Figure 20
Figure 20. Figure 20: Regions of exclusion of points in U p(f). • a diagonal lobe Diag(x, h, w) containing all points diagonally above the box. To define these lobes formally, we first define the upward and downward cones that originate from a particular point. Definition 76. Let x ∈ G be …
Figure 21
Figure 21. Figure 21: Possible configurations of set B defined on a 2-dimensional slice. Definition 82. We define B to contain all points x in the slice s such that f3(x) ≥ x3 and either • x1 = 0 or x2 = 0, or • f3(x − e1 − e2) − x3 < 0 Observe that B contains exactly the set of points for…
Figure 22
Figure 22. Figure 22: Grid states. • b1 = y1 + l or b2 = x2 + l. 4. A full state which consists of a central box (x, h, w) along with all three lobe states: • A left lobe state (x l , hl , wl ) and (y l , ul , vl ) such that x = x l + w l · e1. • A bottom lobe state (x r , hr , wr ) and (y…
Figure 23
Figure 23. Figure 23: Step 1 - Cases 1 and 2.1-2.3 Step 1: Finding a new main lobe. The algorithm first queries the point q = x +  w 2  · e1, which is the point that lies half-way along the bottom side of the main lobe. It then proceeds with the following case analysis, where each case i…
Figure 24
Figure 24. Figure 24: Step 2 - Cases 1,2 and 5 Let (ˆy, u, ˆ vˆ) be the remaining sub-lobe of state t after the original sub-lobe was reduced by removing the points that were ruled out in Step 1. We query the points q bot = x + jw 2 k − h − 1  · e1 + (ˆy2 − x2) · e2, q top = x + jw 2 k …
Figure 25
Figure 25. Figure 25: Sub-Algorithm - Cases 2.5.a and 2.5.b Step 3: Halving the sub-lobe. The final step of the algorithm is to halve the area of the sub-lobe. We need to do this because a significant proportion of the area of t may lie in the sub-lobe, and this area may not have been redu…
Figure 26
Figure 26. Figure 26: Diagonal Lobe State: Step 1 - Cases 1 and 2.1-2.3. [PITH_FULL_IMAGE:figures/full_fig_p063_26.png]
Figure 27
Figure 27. Figure 27: Diagonal Lobe State: Step 2 - Cases 1,2 and 5. [PITH_FULL_IMAGE:figures/full_fig_p064_27.png]
Figure 28
Figure 28. Figure 28: Diagonal Lobe State: Step 3 - Cases 1 and 2. [PITH_FULL_IMAGE:figures/full_fig_p065_28.png]
Figure 29
Figure 29. Figure 29: CB-Config square orientations. The four possible CB-configs are shown in [PITH_FULL_IMAGE:figures/full_fig_p067_29.png]
Figure 30
Figure 30. Figure 30: Direction functions evaluated at a critical box l [PITH_FULL_IMAGE:figures/full_fig_p067_30.png]
Figure 31
Figure 31. Figure 31: Initial configurations of grid square arising fro [PITH_FULL_IMAGE:figures/full_fig_p068_31.png]
Figure 32
Figure 32. Figure 32: Excluded regions from up set search based on config [PITH_FULL_IMAGE:figures/full_fig_p069_32.png]
Figure 33
Figure 33. Figure 33: A depiction of the scheme for left lobe states. [PITH_FULL_IMAGE:figures/full_fig_p072_33.png]
Figure 34
Figure 34. Figure 34: A depiction of the scheme for diagonal-lobe state [PITH_FULL_IMAGE:figures/full_fig_p072_34.png]
Figure 35
Figure 35. Figure 35: The shape of the regions that we consider. [PITH_FULL_IMAGE:figures/full_fig_p073_35.png]
Figure 36
Figure 36. Figure 36: Cases 1 through 4 of the proof of Lemma 68. [PITH_FULL_IMAGE:figures/full_fig_p078_36.png]
Figure 37
Figure 37. Figure 37: Cases 5 through 7 of the proof of Lemma 68. [PITH_FULL_IMAGE:figures/full_fig_p079_37.png]
Figure 38
Figure 38. Figure 38: Cases 8 through 10 of the proof of Lemma 68. [PITH_FULL_IMAGE:figures/full_fig_p079_38.png]
Figure 39
Figure 39. Figure 39: Cases 11 and 12 of the proof of Lemma 68. [PITH_FULL_IMAGE:figures/full_fig_p080_39.png]
Figure 40
Figure 40. Figure 40: The four basic shapes considered. To aid our analysis, we further decompose each valid region into four categories of basic shapes. Specifically we consider spaces that are either box shaped, a lower right-angle triangle with width and height k as shown in [PITH_FULL…
Figure 41
Figure 41. Figure 41: Decomposition of valid regions into at most 5 basi [PITH_FULL_IMAGE:figures/full_fig_p082_41.png]
Figure 42
Figure 42. Figure 42: Removing two triangles from a parallelogram. [PITH_FULL_IMAGE:figures/full_fig_p084_42.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. ARRIVAL: Recursive Framework & $\ell_1$-Contraction

    cs.DS 2025-02 conditional novelty 7.0 of 10

    An algorithm solves ARRIVAL in time 2^{O(k log^2 n)} on n-vertex graphs of treewidth k, and G-ARRIVAL reduces to finding approximate fixed points of l1-contractions.

Reference graph

Works this paper leans on

28 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    Sur les opérations dans les ensembles abs traits et leur application aux équations intégrales

    Stefan Banach. Sur les opérations dans les ensembles abs traits et leur application aux équations intégrales. Fundamenta mathematicae, 3(1):133–181, 1922. 85

    work page 1922

  2. [2]

    Boonyasiriwat, Kris Sikorski, and Ch

    Ch. Boonyasiriwat, Kris Sikorski, and Ch. Xiong. A note o n two fixed point problems. J. Complexity, 23(4-6):952–961, 2007

    work page 2007

  3. [3]

    Improved upper bounds for finding Tar ski fixed points

    Xi Chen and Yuhao Li. Improved upper bounds for finding Tar ski fixed points. In Proc. of EC , pages 1108–1118, 2022

    work page 2022

  4. [4]

    Reducing Tars ki to unique Tarski (in the black-box model)

    Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tars ki to unique Tarski (in the black-box model). In Proc. of CCC , volume 264 of LIPIcs, pages 21:1–21:23, 2023

    work page 2023

  5. [5]

    Computing a fix ed point of contraction maps in polynomial queries

    Xi Chen, Yuhao Li, and Mihalis Yannakakis. Computing a fix ed point of contraction maps in polynomial queries. In Proc. of STOC , pages 1364–1373, 2024

    work page 2024

  6. [6]

    Computations and com plexities of Tarski’s fixed points and supermodular games

    Chuangyin Dang, Qi Qi, and Yinyu Ye. Computations and com plexities of Tarski’s fixed points and supermodular games. CoRR, abs/2005.09836, 2020. Stanford tech report version appea red in 2012

    arXiv 2005

  7. [7]

    Papadimitriou

    Constantinos Daskalakis and Christos H. Papadimitriou . Continuous local search. In Proc. of SODA, pages 790–804, 2011

    work page 2011

  8. [8]

    A Converse to Banach’s Fixed Point Theorem and its CLS Completeness

    Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. A Converse to Banach’s Fixed Point Theorem and its CLS Completeness. In Proc. of STOC , pages 44–50, 2018

    work page 2018

Show all 28 references
  1. [9]

    Papadimitriou, A viad Rubi nstein, and Mihalis Yannakakis

    Kousha Etessami, Christos H. Papadimitriou, A viad Rubi nstein, and Mihalis Yannakakis. Tarski’s theorem, supermodular games, and the complexity of equilib ria. In Proc. of ITCS , volume 151 of LIPIcs, pages 18:1–18:19, 2020

    2020

  2. [10]

    On the complex ity of nash equilibria and other fixed points

    Kousha Etessami and Mihalis Yannakakis. On the complex ity of nash equilibria and other fixed points. SIAM J. Comput. , 39(6):2531–2597, 2010

    2010

  3. [11]

    The complexity of gradient descent: CLS = PPAD ∩ PLS

    John Fearnley, Paul Goldberg, Alexandros Hollender, a nd Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. J. ACM, 70(1):7:1–7:74, 2023

    2023

  4. [12]

    CLS: New problems and complete- ness

    John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Sa vani. CLS: New problems and complete- ness. CoRR, abs/1702.06017, 2017

    2017 arXiv

  5. [13]

    Unique end of potential line

    John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Sa vani. Unique end of potential line. In Proc. of ICALP , volume 132, pages 56:1–56:15, 2019. https://arxiv.org/abs/1811.03841

    2019 arXiv

  6. [14]

    Unique end of potential line

    John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Sa vani. Unique end of potential line. J. Comput. Syst. Sci. , 114:1–35, 2020

    2020

  7. [15]

    A f aster algorithm for finding Tarski fixed points

    John Fearnley, Dömötör Pálvölgyi, and Rahul Savani. A f aster algorithm for finding Tarski fixed points. ACM Trans. Algorithms, 18(3):23:1–23:23, 2022

    2022

  8. [16]

    Tsi- garidas

    Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauri tzen, Peter Bro Miltersen, and Elias P. Tsi- garidas. Exact algorithms for solving stochastic games: ex tended abstract. In Proc. of STOC , pages 205–214, 2011

    2011

  9. [17]

    Tsi- garidas

    Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauri tzen, Peter Bro Miltersen, and Elias P. Tsi- garidas. Exact algorithms for solving stochastic games. CoRR, abs/1202.3898, 2012

    2012 arXiv

  10. [18]

    Huang, Leonid G

    Z. Huang, Leonid G. Khachiyan, and Christopher (Krzysz tof) Sikorski. Approximating fixed points of weakly contracting mappings. J. Complexity , 15(2):200–213, 1999

    1999

  11. [19]

    Prism-games 3.0: Stochas- tic game verification with concurrency, equilibria and time

    Marta Kwiatkowska, Gethin Norman, David Parker, and Ga briel Santos. Prism-games 3.0: Stochas- tic game verification with concurrency, equilibria and time . In Proc. of CAV , volume 12225, pages 475–487, 2020

    2020

  12. [20]

    New algorithms for solving zero-s um stochastic games

    Miquel Oliu-Barton. New algorithms for solving zero-s um stochastic games. Math. Oper. Res. , 46(1):255–267, 2021

    2021

  13. [21]

    Llloyd S. Shapley. Stochastic games*. Proceedings of the National Academy of Sciences , 39(10):1095– 1100, 1953

    1953

  14. [22]

    Shellman and Christopher (Krzysztof) Sikor ski

    Spencer D. Shellman and Christopher (Krzysztof) Sikor ski. A recursive algorithm for the infinity- norm fixed point problem. J. Complex. , 19(6):799–834, 2003. 86

    2003

  15. [23]

    Shellman and Kris Sikorski

    Spencer D. Shellman and Kris Sikorski. A two-dimension al bisection envelope algorithm for fixed points. J. Complexity , 18(2):641–659, 2002

    2002

  16. [24]

    Shellman and Kris Sikorski

    Spencer D. Shellman and Kris Sikorski. Algorithm 825: A deep-cut bisection envelope algorithm for fixed points. ACM Trans. Math. Softw. , 29(3):309–325, 2003

    2003

  17. [25]

    Shellman and Kris Sikorski

    Spencer D. Shellman and Kris Sikorski. Algorithm 848: A recursive fixed-point algorithm for the infinity-norm case. ACM Trans. Math. Softw. , 31(4):580–586, 2005

    2005

  18. [26]

    Computational complexity of fixed points

    Krzysztof Sikorski. Computational complexity of fixed points. Journal of Fixed Point Theory and Applications, 6(2):249–283, 2009

    2009

  19. [27]

    Stochastic games

    Eilon Solan and Nicolas Vieille. Stochastic games. Proceedings of the National Academy of Sciences , 112(45):13743–13746, 2015

    2015

  20. [28]

    A lattice-theoretical fixpoint theorem and its applications

    Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathe- matics, 5(2):285–309, 1955. 87

    1955

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.