PaperlayerView exact revision on arXiv

Source-linked AI summary

Tarski Fixed Points in Quasi-FPT Queries

Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis

arXiv:2610.07055v1cs.CCcs.DS

TL;DR

Finding a Tarski fixed point over [n]^k has had a gap between an Ω(log^2 n) lower bound and log^O(k) n upper bounds. The paper proves improved upper and lower bounds, including a super-polynomial randomized query lower bound even when the function has a unique fixed point.

  • Problem

    The query complexity of finding a Tarski fixed point over [n]^k remained between an Ω(log^2 n) lower bound and log^O(k) n upper bounds.

    Source: §1 · pp. 2–3

  • Method

    The paper gives a deterministic algorithm for Tarski and proves a randomized lower bound, including under the promise of a unique fixed point.

    Source: §1 · p. 3

  • Results

    For k ≥ 3, query complexity is at most O(5^k(log n)^ceil(log k)), while randomized algorithms require (log n)^Omega(log k) queries in expectation, even with a unique fixed point.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The lower bound is the first super-polynomial query lower bound for Tarski fixed points.

    Source: §1 · p. 3

    The paper uses monotone functions for simpler bounds; exploiting the tighter bounds available from restricting to safe functions to improve query complexity remains unclear.

    Source: §2.3 · p. 6

Abstract

from arXiv · show

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$, \[ \Omega\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le \operatorname{Tarski}(n,k)\le O\left(5^k(\log n)^{\lceil \log k\rceil}\right). \] Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n)^{\Theta(\log k )}$. In particular, we obtain the first super-polynomial query lower bound for this problem.

1 Introduction

The paper studies black-box query complexity for finding Tarski fixed points on a grid and improves both prior upper and lower bounds. For k ≥ 3, it gives a deterministic upper bound with logarithmic dependence on k in the exponent of log n and establishes a super-polynomial randomized lower bound, even for functions with a unique fixed point.

Motivation

  • The grid problem captures pure Nash equilibria in supermodular games, several verification games, and the Arrival problem.The paper notes that parity games, mean-payoff games, simple stochastic games, and Arrival are among natural problems that have resisted polynomial-time algorithms.Source: §1 · p. 2

Problem setting

  • The query model gives an algorithm oracle access to an unknown monotone function and asks it to find a fixed point using as few queries as possible.Queries return the entire output vector, may depend on previous answers, and computation between queries is unrestricted.Source: §1 · p. 2

Prior work

  • Earlier bounds ranged from an Ω(log^2 n) lower bound to log^O(k) n upper bounds, with O(log^2 n) algorithms tailored to dimensions three and four.The cited lower bounds include [EPRY20] and; the low-dimensional upper bounds include, [HL26], and [CLY26].Source: §1 · pp. 2–3

Upper bound

  • For k ≥ 3, a deterministic algorithm has query complexity O(5^k(log n)^ceil(log k)).The paper also says this recovers the optimal O(log^2 n) bounds in dimensions three and four within a framework for arbitrary dimensions.Source: §1 · p. 3

Lower bound

  • Randomized algorithms require (log n)^Omega(log k) queries in expectation in the worst case, even when the input has a unique fixed point.This is the first super-polynomial query lower bound for Tarski fixed points.Source: §1 · p. 3

Consequences

  • The lower bound rules out randomized algorithms with query complexity polynomial in k and log n.The paper contrasts this with contraction fixed points under ℓp-norms, which have polynomial-query algorithms for all p ∈ [1, ∞) ∪ {∞}.Source: §1 · p. 3

2 The Algorithm

The algorithm reduces Tarski fixed-point search to a safe-function problem and recursively works toward separating candidate fixed points with opposite labels. Its overview uses heavy antipodal set-pairs to eliminate bad pairs until coordinate separation permits a lower-dimensional recursive call.

2 The Algorithm

  • The paper proves Theorem 2 for Tarski by first stating a main theorem for SafeTarski∗, from which Theorem 2 follows, then combining new ingredients developed across Sections 2.3 to 2.7.Source: §2 · p. 4

2.1 Preliminaries

  • SafeTarski* adds a promise that the monotone function has a unique fixed point on every slice, and it has the same query complexity as Tarski*.The standard binary-search reduction connects Tarski to Tarski* in one fewer dimension.Source: §2.1 · pp. 4–5

2.2 Main theorem and proof overview

  • The algorithm maintains candidate fixed-point sets consistent with the query answers, then separates candidates that can still receive labels −1 and +1.A recursive call to SafeTarski*(n, k−1) finishes once those sets are coordinate-separable.Source: §2.2 · p. 5
  • Bad point-pairs are the obstructions to coordinate separation, so the algorithm measures progress by shrinking their set.A heavy antipodal pair has the property that eliminating either set removes at least a 1/2^k fraction of bad point-pairs.Source: §2.2 · p. 5
  • A recursive SafeTarski* call in dimension ℓ ≤ floor(k/2)−1 can eliminate one set of a heavy antipodal pair; repeating this yields coordinate separation.Once all bad pairs are eliminated, Lemma 9 can be applied to finish the algorithm.Source: §2.2 · p. 6

2.3 Query-answer sets on safe functions

The algorithm uses query answers to bound fixed points of every safe function consistent with the transcript, then shrinks candidate sets until a solution is determined. The bounds use monotone functions for simplicity, although restricting them to safe functions could tighten the bounds.

2.3 Query-answer sets on safe functions

  • Every consistent safe function’s unique fixed point lies between the greatest postfixed point J_s(Q) and least prefixed point M_s(Q) on each slice.The postfixed and prefixed sets are nonempty and closed under coordinatewise joins and meets, respectively.Source: §2.3 · pp. 6–7
  • As queries extend Q, J_s(Q) can only increase and M_s(Q) can only decrease, tightening the bounds on consistent safe functions’ fixed points.The bounds are defined using monotone functions rather than only safe functions; restricting to safe functions could tighten them, but the authors do not know how to exploit that for lower query complexity.Source: §2.3 · pp. 6–7

2.4 Candidate fixed points

  • Fix(Q) contains the unique fixed point of every safe function consistent with Q and is characterized by the slice-wise bounds J_s(Q) ⪯ x ⪯ M_s(Q).The extreme points J(Q) and M(Q) also belong to Fix(Q).Source: §2.4 · pp. 7–8
  • If every consistent monotone function forces a strict coordinate inequality at x, then x is excluded from Fix(Q).The exclusion follows by using a one-dimensional slice to derive a postfixed or prefixed bound that x violates.Source: §2.4 · p. 8
  • As queries accumulate, Fix−(Q) and Fix+(Q) only shrink; if either becomes empty, J(Q) or M(Q) is already a solution for every consistent safe function.An empty Fix−(Q) yields a positive solution at J(Q); an empty Fix+(Q) yields a negative solution at M(Q).Source: §2.4 · pp. 8–9

2.5 Dimension reduction via coordinate separation

The algorithm aims to make the positive and negative candidate sets coordinate-separable. Once they are separated along coordinate k, it reduces the problem to a slice with k−1 free coordinates and finds a solution with at most SafeTarski*(n, k−1) + 1 additional queries.

2.5 Dimension reduction via coordinate separation

  • The strategy shrinks Fix−(Q) and Fix+(Q) while aiming to make them coordinate-separable, so that one set can be eliminated and a solution obtained.Coordinate-separability means the sets can be separated by a threshold in coordinate k.Source: §2.5 · p. 9
  • When Fix−(Q) and Fix+(Q) are coordinate-separable, a solution can be found with at most SafeTarski*(n, k −1) + 1 additional queries.The algorithm applies SafeTarski* to an induced function on the slice whose k-th coordinate is fixed at the separating threshold.Source: §2.5 · pp. 9–10
  • Simulating the lower-dimensional algorithm and querying its returned point reveals a solution through the resulting coordinate inequalities or label.The proof treats four cases according to whether the queried output is above, below, or at the threshold and its label.Source: §2.5 · p. 10

2.6 Existence of a heavy antipodal set-pair

For any nonempty set of bad point-pairs, the proof constructs an antipodal pair of subsets that retains a substantial fraction of those pairs. The pair’s threshold structure supports the later elimination algorithm.

2.6 Existence of a heavy antipodal set-pair

  • Eliminating either set of a heavy pair reduces the number of bad point-pairs by at least a 1/2k fraction.The antipodal structure is used by the subsequent algorithm to eliminate one set with few queries.Source: §2.6 · p. 10
  • A heavy antipodal pair S− ⊆ Fix−(Q) and S+ ⊆ Fix+(Q) retains at least a 2^-k fraction of the bad pairs in each associated pair set.The pair is antipodal with respect to a threshold vector, with the k-th coordinate separated in the specified direction.Source: §2.6 · pp. 10–11
  • The construction processes coordinates one at a time, restricting each pair set to at least half its pairs while preserving earlier coordinate inequalities.It begins by splitting bad pairs according to a median value in coordinate k.Source: §2.6 · p. 11

2.7 Eliminating one set from an antipodal set-pair

The algorithm eliminates one side of an antipodal set-pair by solving an induced lower-dimensional SafeTarski* instance. It needs at most SafeTarski*(n, ⌊k/2⌋−1) + 1 additional queries.

2.7 Eliminating one set from an antipodal set-pair

  • At most SafeTarski*(n, ⌊k/2⌋−1) + 1 additional queries suffice to eliminate S− from Fix−(Q′) or S+ from Fix+(Q′).The guarantee holds for nonempty subsets S− and S+ forming an antipodal pair.Source: §2.7 · p. 12
  • For a nonempty J, the algorithm fixes coordinates on a slice and induces a safe instance with min{|J|, |H|} −1 free coordinates.It simulates the induced instance using oracle queries to the original function; when the minimum is zero, querying the threshold suffices.Source: §2.7 · p. 12
  • The induced instance’s returned point yields a query-answer pair whose coordinate inequalities or label rule out one antipodal set.The proof handles the two relative sizes of J and H separately, using monotonicity and the exclusion properties of Fix(Q).Source: §2.7 · pp. 13–14

2.8 Putting everything together

The proof repeatedly shrinks the set of bad point-pairs until none remain, then either finishes immediately or solves the remaining coordinate-separable problem. Expanding the resulting recurrence gives the stated query-cost bound.

2.8 Putting everything together

  • Each round uses a heavy antipodal set-pair to reduce the bad-pair set by at least a 1/2^k fraction, at a cost of at most SafeTarski*(n, floor(k/2)−1)+1 queries.Since the initial set has at most n^(2k) pairs, the proof repeats this reduction until no bad pairs remain.Source: §2.8 · p. 14
  • After bad pairs are eliminated, an empty Fix−(Q) or Fix+(Q) finishes the problem; otherwise coordinate separation allows completion in at most SafeTarski*(n, k−1)+1 queries.Source: §2.8 · p. 14
  • The proof combines these phases into a recurrence and expands its first term through dimensions k−1 down to 2, using that SafeTarski*(n, d) is nondecreasing in d.The passage states that this yields a total query-cost bound but does not include its expression.Source: §2.8 · p. 14

3 The Lower Bound

The lower-bound proof builds distributions of monotone functions through an inductive amplification, then applies Yao’s minimax principle. The resulting argument establishes a randomized query lower bound even when the input has a unique fixed point.

3 The Lower Bound

  • Yao’s minimax principle converts the distributional lower bound into a worst-case lower bound for randomized algorithms, including inputs promised to have a unique fixed point.Source: §3 · pp. 14–15
  • Each induction level composes a one-dimensional hidden-number search, requiring Ω(log m) queries, with a lower-level instance to amplify the bound.The amplification increases the lower bound by an Ω_ℓ(log m) factor.Source: §3 · p. 15
  • Theorem 6 constructs distributions of monotone functions on parameterized grids where shallow deterministic decision trees find the fixed point only with small probability.The supplied theorem passage omits the full probability and depth expressions.Source: §3 · p. 15
  • Padding the constructed grids and adding constant coordinates preserve monotonicity and the unique fixed point, while each padded query simulates one original query.Source: §3 · p. 15

3.1 The base case: a distribution of two-dimensional monotone functions

The base case uses the two-dimensional herringbone construction of Etessami, Papadimitriou, Rubinstein, and Yannakakis [EPRY20] to obtain a hard distribution with unique fixed points.

3.1 The base case: a distribution of two-dimensional monotone functions

  • The construction starts from the two-dimensional herringbone construction of Etessami, Papadimitriou, Rubinstein, and Yannakakis [EPRY20], and gives the desired bound for ℓ=1 with k1=2 dimensions.Source: §3.1 · p. 16
  • For m≥200, the [EPRY20] distribution over monotone functions [m]^2→[m]^2 has a unique fixed point for every function in its support.Source: §3.1 · p. 16
  • At depth q=c0(log m)^2, a deterministic decision tree finds the fixed point with probability at most m^(−c0−1).Source: §3.1 · p. 16

3.2 The amplification step

The amplification step turns a distribution of unique-fixed-point instances into a harder, higher-dimensional distribution. It places candidate fixed points in a common antichain, hides a bit at the fixed point, and combines two sign coordinates to maintain monotonicity and uniqueness.

3.2 The amplification step

  • The amplification maps an input distribution H to a distribution of functions whose support still has unique fixed points.Source: §3.2 · p. 16

3.2.1 Step 1: putting all candidate fixed points in an anti-chain

  • Applying H independently to two coordinate blocks gives GH a unique fixed point at (PH, PH), placing the candidate in the fixed antichain C.Source: §3.2.1 · pp. 16–17

3.2.2 Step 2: Hiding one new bit in a sign function

  • The sign function hides bit c except at the unique fixed point, so learning c requires finding and querying that point.Source: §3.2.2 · p. 17

3.2.3 A failed attempt to put the first two steps together

  • Combining the first two steps in one sign coordinate risks violating monotonicity because hiding t* can require displacements −1, 0, and 1.Source: §3.2.3 · p. 18

3.2.4 Step 3: Defining the new distribution of monotone functions

  • The new construction uses 4k+2 dimensions, samples m independent instances from H, and hides a uniformly chosen t* in [m].The construction separates sign coordinates from value coordinates and uses boxes for the value-coordinate groups.Source: §3.2.4 · p. 18
  • Updates in opposite directions on the two sign coordinates avoid the single-coordinate displacement conflict; swapping them keeps the diagonal fixed and singles out (t*, t*) as the unique sign-coordinate fixed point.Source: §3.2.4 · pp. 18, 20, Figure 1 · p. 19

3.3 Basic properties of the constructed distribution of functions

The constructed distribution consists of functions with a unique fixed point, and every function in its support is monotone. The uniqueness proof identifies the fixed point using the hidden index and the sampled function at that index.

3.3.1 Uniqueness of the fixed point

  • Every constructed function has the unique fixed point (t*, t*, P*, P*).The proof shows that any fixed point must have a=b=t* and X=Y=P*; it also verifies that this tuple is a fixed point.Source: §3.3.1 · pp. 20–21
  • The unique fixed point uses the sampled function's fixed point at the hidden index t*, shifted into the corresponding block in both coordinate halves.The proof verifies the resulting P* is fixed by the constructed function at that index.Source: §3.3.1 · p. 20

3.3.2 Monotonicity

  • Every function in the support of the constructed distribution is monotone.The proof checks that increasing one coordinate of the input cannot decrease the output, establishing monotonicity across the cases considered.Source: §3.3.2 · pp. 21–22

3.4 Query lower bound for the constructed distribution of functions

The lower-bound construction amplifies a hard distribution while preserving monotonicity and a unique fixed point. Its analysis bounds how often decision trees can find that fixed point by tracking their ability to learn a hidden index.

3.4 Query lower bound for the constructed distribution of functions

  • Theorem 6 constructs distributions of monotone functions on [n_l,m]^k_l, with n_l,m=m^l and k_l=2(4^l−1)/3, whose unique fixed points are hard to find.For decision trees of depth q_l,m, the theorem bounds the probability of finding the unique fixed point by ε_l,m.Source: §3.4 · pp. 22, 25
  • The amplification lemma bounds a decision tree's success probability by 1/√m + qε for the amplified distribution.The lemma's bound combines the chance of learning the hidden index with the induction-hypothesis bound for the base distribution.Source: §3.4 · pp. 23, 25
  • Each query to the amplified function can be determined using at most four queries to the sampled base functions, and hidden signs are revealed only under fixed-point projection conditions.This limits how much information a decision tree gains about the hidden index from its queries.Source: §3.4 · p. 23
  • Finding the constructed function's unique fixed point requires learning the hidden index t*, so the proof bounds success by the probability of identifying t*.When queries reveal at most 0.5 log m hidden signs, the probability of finding t* is at most 1/√m.Source: §3.4 · p. 23

A Proof of Theorem 2

The proof derives the upper bound by solving a recurrence for SafeTarski* and applying Theorem 4. Its induction yields the logarithmic exponent and the 5^k factor in the resulting query bound.

A Proof of Theorem 2

  • The induction establishes SafeTarski*(n,r) ≤ A5^r(log n)^e(r), where e(r)=ceil(log((r+3)/3)).The base cases are SafeTarski*(n,0)=1 and SafeTarski*(n,1)=O(log n).Source: A Proof of Theorem 2 · p. 28
  • The proof combines the recurrence bound with Theorem 4, then uses a dimension inequality to obtain the final exponent.For j=ceil(log k), the proof uses k+2 ≤ 3·2^(j−1).Source: A Proof of Theorem 2 · p. 29
  • The proof concludes with an upper bound of O(5^k(log n)^ceil(log k)) for Tarski(n,k).The proof states that the factor 5^k can be replaced by C^k for any fixed C>4.Source: A Proof of Theorem 2 · pp. 28–29
Loading 2610.07055v1…