ARRIVAL: Recursive Framework & $\ell_1$-Contraction

Sebastian Haslebacher

REVIEW 2 major objections 5 minor 15 references

ARRIVAL: Recursive Framework & $\ell_1$-Contraction

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

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

Pith's one-line read This paper proves a treewidth-parameterized quasi-polynomial algorithm for the ARRIVAL game and reduces its generalization to ℓ1-contraction fixed points.

desk verdict The treewidth algorithm is genuinely new and worth refereeing, but the written proof has a load-bearing gap—Lemma 2 gives a false linear bound—which has a clean exponential fix that preserves the stated runtime. read the letter →

arxiv 2502.06477 v2 pith:XBMY3C3Z submitted 2025-02-10 cs.DS

Sebastian Haslebacher This is my paper · ORCID

classification cs.DS

keywords ARRIVALG-ARRIVALswitchingflowtreewidthbalancedseparatorell1-contractionfixedpointzero-playergame

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

ARRIVAL is a deterministic zero-player token game whose decision problem lies in NP∩coNP but is not known to be in P. This paper establishes that on n-vertex instances of treewidth k, ARRIVAL can be solved in time $2^{O(k\log^2 n)}$, which is quasi-polynomial for every fixed k. The algorithm works on a multi-token generalization, G-ARRIVAL, by recursively guessing the outflow of a pivot vertex and verifying the guess with a binary search; balanced separators drive the recursion to split the instance. The same recursive framework also reproduces the best-known subexponential bound. A second result reduces G-ARRIVAL to finding an approximate fixed point of an $\ell_1$-contracting function, so any polynomial fixed-point finder for such maps would put G-ARRIVAL in P.

What carries the argument

The load-bearing object is the switching flow: a nonnegative assignment to the edges that obeys alternating behavior at each vertex, flow conservation at non-terminals, and prescribed outflow at terminals. Theorem 1 makes any integral switching flow a certificate for the terminal counts. Around it, the paper builds two mechanisms: a pivot binary-search recursion that converts one non-terminal into a terminal and guesses its outflow, and the one-step update function $f(x)_v = \sum_{u:s_0(u)=v} h_0(x_u) + \sum_{u:s_1(u)=v} h_1(x_u)$, where $h_0,h_1$ split each vertex's token mass between its two outgoing edges. Projected to non-terminals and multiplied by a discount factor $\lambda<1$, this map becomes an $\ell_1$-contraction whose unique fixed point sits below every fixed point of the undiscounted map, and a sufficiently accurate approximation of that fixed point determines the G-ARRIVAL answer.

What would settle it

Search exhaustively over small switch graphs and token counts for an integral switching flow with $x(e) \ge 2|V|t_+$ on some edge $e$. Finding one would refute the stated Lemma 2 and break the binary-search range in Algorithm 1 and Algorithm 2; finding none on modest sizes would support the lemma but would not prove it.

Watch

Extended reading notes

Core claim

The central claim is that G-ARRIVAL—and therefore ARRIVAL—admits algorithms whose running time is controlled by the treewidth k of the underlying undirected graph. Concretely, the paper proves Theorem 10: given a smallest balanced separator of G−T, Algorithm 2 computes an integral switching flow in time $2^{O(k\log(|V\setminus T|)\log(|V|+\log t_+))}$, which for ARRIVAL is $2^{O(k\log^2 n)}$. An integral switching flow is the key certificate: by a theorem of Dohrau et al., any integral switching flow determines exactly how many tokens arrive at each terminal, so solving G-ARRIVAL reduces to finding one. The algorithm's correctness rests on a binary search over one vertex's outflow using the monotonicity of the terminal-count map, and its efficiency rests on balanced separators of size at most k+1 that exist in every subgraph of a treewidth-k graph. The paper also claims a reduction from G-ARRIVAL to the approximate fixed-point problem for $\ell_1$-contractions, showing the fixed point of the appropriately discounted one-step update reveals the terminal counts.

Load-bearing premise

The search range assumes that no edge is ever used more than $2|V|t_+$ times in any valid flow of tokens, but the supplied proof only shows a far weaker exponential bound; if the stronger bound is false, the termination argument for the binary search as written fails.

Editorial extensions

If this is right

For every fixed treewidth k, ARRIVAL can be decided in quasi-polynomial time $2^{O(k\log^2 n)}$, improving the previous $2^{O(\sqrt{n}\log n)}$ bound on bounded-treewidth graphs.
The recursive framework yields the prior subexponential bound and a polynomial bound on graphs with bounded feedback vertex set as special instantiations.
A polynomial algorithm for finding approximate fixed points of $\ell_1$-contractions would immediately give a polynomial algorithm for G-ARRIVAL and hence for ARRIVAL.
The reduction supplies the first natural application of the $\ell_1$-contraction fixed-point problem, whose query complexity has recently been shown to be polynomial.
ARRIVAL now matches known treewidth-parameterized results for Simple Stochastic Games, reinforcing the long-suspected parallel between the two problems.

Reading between the lines

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

The paper does not pursue time-efficient fixed-point algorithms itself; if such algorithms for monotone $\ell_1$-contractions appear, this reduction could turn into a polynomial ARRIVAL algorithm.
The stated linear edge-flow bound is used only to set the binary-search range; replacing it by the proven exponential bound would change only logarithmic factors in the stated runtime, so the main treewidth result should survive a repair of that lemma.
The balanced-separator framework looks portable: any parameter that guarantees small separators in subgraphs of the input could plug into Algorithm 2 and yield an analogous quasi-polynomial bound.

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.

Desk Editor's Note

read the letter

Quick take: the paper is worth reading and worth refereeing. The bounded-treewidth algorithm for ARRIVAL is a real new result, and the recursive framework around it is clean. The reduction to ell_1-contraction fixed points is also a new and interesting connection. But the written proof has a genuine gap, and the stress-test note correctly identifies it: Lemma 2's halving argument only establishes an exponential bound, and the stated linear bound 2|V|t+ is actually false for t+=1 when run profiles get long. Since Algorithms 1 and 2 set their binary search range to exactly 2|V|t+, the correctness proofs of Lemma 5, Lemma 8, and Theorem 10 fail as written. The fix is straightforward: take r=2^{O(|V|)}t+ instead, and the advertised runtime 2^{O(k log n log(n+log t+))} should survive, because log r only adds O(|V|) to the token-count bound and the recursion-depth factor already absorbs that. The ell_1-contraction reduction is a nice novel angle: discount the one-step update, get a Banach fixed point, and use it to read off the answer. But the step from the fixed point to individual terminal counts in Theorem 19 is under-specified. Lemma 18 proves only a total lower bound on terminal inflow, and the rounding argument that yields each t^-_v is sketched rather than proved. It is probably repairable, but a referee should ask for the full argument. What the paper does well: the algorithm is a genuine contribution that matches the SSG treewidth result, the framework rederives the known subexponential and feedback-vertex-set bounds, and the exposition is mostly clear. The citation of [16] is self-citation, but it points to a published prerequisite and the dependency is honest. No code or formal verification accompanies the paper, so the proof carries the weight—which makes the Lemma 2 gap matter. Who it is for: researchers in ARRIVAL, TFNP, or parameterized algorithms for zero-player games. It deserves a serious referee. I would not desk-reject it; the main idea is plausible and likely correct after repairs. The right outcome is a conditional accept that requires the Lemma 2 fix and a more detailed fixed-point-to-answer proof.

Referee Report

2 major / 5 minor

Summary. The paper studies ARRIVAL and its generalization G-ARRIVAL. It proposes a recursive algorithm that guesses the outflow of a pivot vertex and verifies the guess by binary search; choosing pivots from balanced separators yields a 2^{O(k log^2 n)}-time algorithm on n-vertex graphs of treewidth k. The paper also constructs an ℓ1-contracting function whose unique fixed point encodes the answer to a G-ARRIVAL instance, yielding a reduction to approximate fixed-point computation. The recursive framework is used to rederive the subexponential algorithm of Gärtner et al. [16] and to point out parallels with Simple Stochastic Games.

Significance. If the proofs are repaired, the treewidth bound would be a genuine advance: prior work gave a 2^{O(sqrt(n) log n)} algorithm and polynomial-time algorithms only on very restricted graph classes, while no quasi-polynomial bound for bounded-treewidth ARRIVAL was known. The ℓ1-contraction reduction is also novel and, combined with query-efficient algorithms for ℓ1-contractions or future time-efficient versions, could lead to new algorithms for ARRIVAL. The paper is clearly organized and provides useful context linking ARRIVAL to SSG. However, the written proofs contain load-bearing gaps, mainly around Lemma 2 and the separator invariant in Algorithm 2, that must be fixed before the main claims can be accepted.

major comments (2)

[Section 2, Lemma 2; Algorithms 1 and 2] The stated bound x(e) < 2|V|t+ is not what the proof establishes. The halving argument along a simple path of length at most |V|-1 starting from x(e) ≥ A gives x^-(v_k) ≥ A/2^k, so to force x^-(v_k) > t+ one needs A = 2^{|V|}t+, not A = 2|V|t+. The claimed linear bound is also false as a mathematical statement: for t+ = 1 the run profile of an ARRIVAL instance can traverse an edge more than 2|V| times, since the deterministic process may take exponentially many steps. This bound is load-bearing: the binary search ranges r = 2|V|t+ in Algorithm 1 (line 10) and Algorithm 2 (line 13), and the correctness arguments in Lemma 5 and Lemma 8, rely on it. The paper itself uses the exponential bound ||x*|| ≤ n 2^n t+ in Theorem 19, showing an internal inconsistency. The results are likely repairable by setting r = 2^{O(|V|)} t+; the logarithms in the runtime analyses then remain O(log(|V| + log t+)), but the statements and proofs must be corrected.
[Section 3.3, Lemma 9 and Theorem 10] The runtime analysis assumes that after at most k+1 binary-search steps the splitting case halves the number of non-terminals. However, Algorithm 2 does not recompute a balanced separator when a pivot is added to T; it only removes the pivot from S. At the splitting case S = ∅, the remaining graph G−T is the graph obtained from the call's initial instance by deleting all of the initial separator, so a connected component may have size up to half of the initial non-terminal count, not half of the current non-terminal count. Hence Lemma 9's second sentence, as written, is false, and the recurrence T(|V\T|,0) ≤ ... T(|V\T|/2, k+1) in Theorem 10 is unsupported. A correct analysis can probably be given by measuring progress in blocks, where each block deletes at most k+1 separator vertices and then reduces the non-terminal count by a factor of two relative to the block's start, but the proof needs to be rewritten.

minor comments (5)

[Section 2, Lemma 2 proof] The notation '2|V|−i' should be typeset as 2^{|V|-i}; the current rendering is ambiguous and should be fixed.
[Algorithms 1 and 2] If the binary search range is corrected to r = 2^{O(|V|)} t+, the comments and variable names in the pseudocode should be updated to match the corrected bound.
[Section 4, near Lemma 18] The notation g(x̂)_v for v ∈ T is used without a formal definition; the projection g was defined only on non-terminal coordinates, so the intended meaning should be made explicit.
[Lemma 5 proof] The sentence ending with 'using Lemma 2' when deriving x^-(p) ≤ t+_p should cite the total-arrivals equation from Theorem 1 rather than the edge bound from Lemma 2, since the edge bound is not needed there.
[Abstract and Section 1] The text says the reduction is 'to finding a fixed point', but Theorem 19 is a reduction to finding an approximate fixed point; the terminology should be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the recursive framework and the ℓ1-contraction reduction are self-contained transformations, and the disputed Lemma 2 bound is a correctness concern rather than a circular derivation.

full rationale

The paper's central algorithms are not circular. Algorithm 1 guesses the outflow of a pivot vertex, converts that vertex into a terminal, solves the augmented instance recursively, and checks whether the returned inflow matches the guess. A consistent guess exists because any original integral switching flow is also a feasible flow for the augmented instance, so the verification step is a genuine induction rather than a definitional identity. The parameterized recurrence in Algorithm 2 and Theorem 10 uses the balanced-separator lemma from the textbook [10] together with the monotonicity lemma cited from Gärtner et al. [16]. Although [16] shares an author with the present paper, Lemma 4 is a published prerequisite and not the claimed target result, and the algorithm's new contribution is the separator-based recursion and its analysis. The self-citations to Lemmas 6 and 7 of [16] are used only to rederive known subexponential and bounded-feedback-vertex-set bounds, not to establish Theorem 10. The reduction in Section 4 is also substantive rather than circular: the one-step update function is explicitly built from the switching rules, Lemma 14 proves an equivalence between integral fixed points and integral switching flows, and the discounted function is then shown to carry enough information to recover terminal inflows. This connects G-ARRIVAL to ℓ1-contraction as a real reduction, not as a restatement of the input. The reader's and skeptic's concerns about Lemma 2 are correctness issues, not circularity: the proof sketch appears to support an exponential bound rather than the stated linear bound x(e)<2|V|t+, and this may affect the binary-search range in Algorithms 1 and 2. However, an unsupported or false intermediate bound is not an instance of a prediction being equivalent to an input by construction. The paper also explicitly notes that the query-efficient ℓ1-fixed-point algorithm of [18] is not time-efficient, so its reduction currently yields no runtime improvement; this is an honest limitation, not a circular step. No load-bearing step reduces, by the paper's own equations or by self-citation, to its own inputs.

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

No free parameters are fitted to data; the algorithm's binary search range and the contraction parameter lambda are construction choices, not fitted values. The load-bearing axioms are prior theorems from the literature, with the switching-flow bound being the fragile one.

assumptions (5)

domain assumption Integral switching flows are certificates: any integral switching flow predicts terminal arrivals (Theorem 1).
Proven in Dohrau et al. [11]; the paper relies on it throughout to justify solving G-ARRIVAL by finding any integral switching flow.
domain assumption Monotonicity of G-ARRIVAL: increasing starting tokens at a terminal cannot decrease ending tokens at any terminal (Lemma 4).
Quoted from Gaertner et al. [16], a paper with overlapping authorship; used to justify binary search over the guessed outflow of the pivot.
standard math Every graph of treewidth k has a balanced separator of size at most k+1 in every induced subgraph (Lemma 3).
From Cygan et al. [10, Lemma 7.19]; standard graph-theoretic result used to bound recursion depth.
domain assumption Lemma 2: any integral switching flow has edge values below 2|V|t+.
Attributed to [11] with a sketch; the sketch appears inconsistent with the exponential bound used in Theorem 19. This is the weakest assumption.
standard math Banach fixed point theorem guarantees a unique fixed point of l1-contractions.
Used in Section 4 for the discounted one-step update.

how reviews work

0 comments

Cite this review

Pith. "Pith review of ARRIVAL: Recursive Framework & $\ell_1$-Contraction." pith.science (2026). https://pith.science/paper/XBMY3C3Z

@misc{pith2026250206477,
  author       = {Pith},
  title        = {Pith review of: ARRIVAL: Recursive Framework & $\ell_1$-Contraction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XBMY3C3Z}},
  note         = {Machine review of arXiv:2502.06477}
}

abstract

ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, according to so-called switching rules. It is known to lie in NP $\cap$ CoNP, but not known to lie in P. The state-of-the-art algorithm due to G\"artner et al. (ICALP `21) runs in time $2^{O(\sqrt{n} \log n)}$ on an $n$-vertex graph. We prove that ARRIVAL can be solved in time $2^{O(k \log^2 n)}$ on $n$-vertex graphs of treewidth $k$. Our algorithm is derived by adapting a simple recursive algorithm for a generalization of ARRIVAL called G-ARRIVAL. This simple recursive algorithm acts as a framework from which we can also rederive the subexponential upper bound of G\"artner et al. Our second result is a reduction from G-ARRIVAL to the problem of finding an approximate fixed point of an $\ell_1$-contracting function $f : [0, 1]^n \rightarrow [0, 1]^n$. Finding such fixed points is a well-studied problem in the case of the $\ell_2$-metric and the $\ell_\infty$-metric, but little is known about the $\ell_1$-case. Both of our results highlight parallels between ARRIVAL and the Simple Stochastic Games (SSG) problem. Concretely, Chatterjee et al. (SODA `23) gave an algorithm for SSG parameterized by treewidth that achieves a similar bound as we do for ARRIVAL, and SSG is known to reduce to $\ell_\infty$-contraction.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

[1]

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

1 David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. LIPIcs, Volume 241, MFCS 2022, 241:12:1–12:14,

work page 2022
[11]

arXiv:2503.16089, doi:10.48550/arXiv.2503. 16089. 19 Hung P. Hoang.On Two Combinatorial Reconfiguration Problems: Reachability and Hamilton- icity. Doctoral Thesis, ETH Zurich, 2022.doi:10.3929/ethz-b-000572947. 20 Karthik C. S. Did the Train Reach its Destination: The Complexity of Finding a Witness. Information Processing Letters, 121:17–21, May 2017.do...

work page Pith review arXiv doi:10.48550/arxiv.2503.16089 2022
[14]

26 Thomas Webster

Springer International Publishing.doi:10.1007/978-3-031-19135-0_7. 26 Thomas Webster. The Recursive Arrival Problem. Electronic Proceedings in Theoretical Computer Science, 390:168–184, September

work page doi:10.1007/978-3-031-19135-0_7
[15]

arXiv:2310.01004, doi:10.4204/EPTCS. 390.11

work page Pith review arXiv
[1013]

Computational complexity of fixed points.Journal of Fixed Point Theory and Applications, 6(2):249–283, December 2009.doi:10.1007/s11784-009-0128-3

24 Krzysztof Sikorski. Computational complexity of fixed points.Journal of Fixed Point Theory and Applications, 6(2):249–283, December 2009.doi:10.1007/s11784-009-0128-3. 25 Thomas Webster. The Stochastic Arrival Problem. InReachability Problems, pages 93–107, Cham,

work page doi:10.1007/s11784-009-0128-3 2009
[1922]

Monotone Contractions

doi:10.4064/fm-3-1-133-181. 5 Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Monotone Contractions, November 2024.arXiv:2411.10107, doi:10.48550/arXiv.2411.10107. 6 Krishnendu Chatterjee and Nathanaël Fijalkow. A Reduction from Parity Games to Simple Stochastic Games. InInternational Symposium on Games, Automata, Logics, and F...

work page Pith review arXiv doi:10.48550/arxiv.2411.10107 2024
[1996]

18 ARRIVAL: Recursive Framework & ℓ1-Contraction 23 K

doi:10.1103/PhysRevLett.77.5079. 18 ARRIVAL: Recursive Framework & ℓ1-Contraction 23 K. Sikorski, C.W. Tsay, and H. Woźniakowski. An Ellipsoid Algorithm for the Computation of Fixed Points.Journal of Complexity, 9(1):181–200, March 1993.doi:10.1006/jcom.1993

doi:10.1103/physrevlett.77.5079
[2017]

12 Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis

doi:10.1007/978-3-319-44479-6_14. 12 Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:19, ...

work page doi:10.1007/978-3-319-44479-6_14

Show all 15 references

[2018]

16 Bernd Gärtner, Sebastian Haslebacher, and Hung P

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.doi:10.4230/LIPIcs.ICALP.2018.60. 16 Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A Subexponential Algorithm for ARRIVAL. In48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 1...

2018 doi
[2020]

13 John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.doi:10.4230/LIPIcs.ITCS.2020.18. 13 John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability Switching Games. Logical Methods in Computer Science, Volume 17, Issue 2, April 2021.doi:10.23638/ LMCS-17(2:10)20...

2020 doi
[2021]

doi:10.4230/LIPIcs.ICALP.2021.69

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.69. 17 Ebrahim Ghorbani, Jonah Leander Hoff, and Matthias Mnich. A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs. In42nd International Symposium on Theoretical Aspects...

2021 doi
[2022]

2 David Auger, Pierre Coucheney, Loric Duhazé, and Kossi Roland Etse

doi: 10.4230/LIPICS.MFCS.2022.12. 2 David Auger, Pierre Coucheney, Loric Duhazé, and Kossi Roland Etse. Generalized ARRIVAL Problem for Rotor Walks in Path Multigraphs. InReachability Problems, pages 183–198, Cham,

2022 doi
[2023]

3 David Auger, Pierre Coucheney, and Yann Strozecki

Springer Nature Switzerland.doi:10.1007/978-3-031-45286-4_14. 3 David Auger, Pierre Coucheney, and Yann Strozecki. Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games. InTheory and Applications of Models of Computation, volume 8402, pages 67–85. Springer Inter...

doi
[2024]

doi:10.1145/3618260.3649623

Association for Computing Machinery. doi:10.1145/3618260.3649623. 9 Anne Condon. The Complexity of Stochastic Games.Information and Computation, 96(2):203– 224, February 1992.doi:10.1016/0890-5401(92)90048-K. 10 Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, D...

1992
[2025]

18 Sebastian Haslebacher, Jonas Lill, Patrick Schnider, and Simon Weber

Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.STACS.2025.39. 18 Sebastian Haslebacher, Jonas Lill, Patrick Schnider, and Simon Weber. Query-Efficient Fixpoints of ℓp-Contractions, March

2025 doi

Pith tools

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

[1] [1]

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

1 David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. LIPIcs, Volume 241, MFCS 2022, 241:12:1–12:14,

work page 2022

[2] [11]

arXiv:2503.16089, doi:10.48550/arXiv.2503. 16089. 19 Hung P. Hoang.On Two Combinatorial Reconfiguration Problems: Reachability and Hamilton- icity. Doctoral Thesis, ETH Zurich, 2022.doi:10.3929/ethz-b-000572947. 20 Karthik C. S. Did the Train Reach its Destination: The Complexity of Finding a Witness. Information Processing Letters, 121:17–21, May 2017.do...

work page Pith review arXiv doi:10.48550/arxiv.2503.16089 2022

[3] [14]

26 Thomas Webster

Springer International Publishing.doi:10.1007/978-3-031-19135-0_7. 26 Thomas Webster. The Recursive Arrival Problem. Electronic Proceedings in Theoretical Computer Science, 390:168–184, September

work page doi:10.1007/978-3-031-19135-0_7

[4] [15]

arXiv:2310.01004, doi:10.4204/EPTCS. 390.11

work page Pith review arXiv

[5] [1013]

Computational complexity of fixed points.Journal of Fixed Point Theory and Applications, 6(2):249–283, December 2009.doi:10.1007/s11784-009-0128-3

24 Krzysztof Sikorski. Computational complexity of fixed points.Journal of Fixed Point Theory and Applications, 6(2):249–283, December 2009.doi:10.1007/s11784-009-0128-3. 25 Thomas Webster. The Stochastic Arrival Problem. InReachability Problems, pages 93–107, Cham,

work page doi:10.1007/s11784-009-0128-3 2009

[6] [1922]

Monotone Contractions

doi:10.4064/fm-3-1-133-181. 5 Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Monotone Contractions, November 2024.arXiv:2411.10107, doi:10.48550/arXiv.2411.10107. 6 Krishnendu Chatterjee and Nathanaël Fijalkow. A Reduction from Parity Games to Simple Stochastic Games. InInternational Symposium on Games, Automata, Logics, and F...

work page Pith review arXiv doi:10.48550/arxiv.2411.10107 2024

[7] [1996]

18 ARRIVAL: Recursive Framework & ℓ1-Contraction 23 K

doi:10.1103/PhysRevLett.77.5079. 18 ARRIVAL: Recursive Framework & ℓ1-Contraction 23 K. Sikorski, C.W. Tsay, and H. Woźniakowski. An Ellipsoid Algorithm for the Computation of Fixed Points.Journal of Complexity, 9(1):181–200, March 1993.doi:10.1006/jcom.1993

doi:10.1103/physrevlett.77.5079

[8] [2017]

12 Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis

doi:10.1007/978-3-319-44479-6_14. 12 Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:19, ...

work page doi:10.1007/978-3-319-44479-6_14