Randomized Lower Bounds for Tarski Fixed Points in High Dimensions
Simina Brânzei Reed Phillips Nicholas Recker




Foundation Model or Finetune? Evaluation of few-shot semantic segmentation for river pollution
    Marga Don10009-0001-5435-8935 
Stijn Pinson 2 Blanca Guillen Cebrian 2
Yuki M. Asano 1,3 


    September 9, 2024
===============================================================================================




§ ABSTRACT 
The Knaster-Tarski theorem, also known as Tarski's theorem,  guarantees that every monotone function defined on a complete lattice has a fixed point. 
We analyze the query complexity of finding such a fixed point on the 
k-dimensional grid of side length n under the 
≤ relation. Specifically, there is an unknown monotone function f: {0,1,…, n-1}^k →{0,1,…, n-1}^k and an algorithm must query a vertex v to learn  f(v).

 Our main result is a randomized lower bound of Ω( k + k ·logn/logk) for  the k-dimensional grid of side length n, which is nearly optimal in high dimensions when k is large relative to n. As a corollary, we  characterize  the randomized and deterministic query complexity   of the Tarski search problem on the Boolean hypercube {0,1}^k as  Θ(k).







§ INTRODUCTION


The Knaster-Tarski theorem, also known as Tarski's theorem, guarantees that every monotone function f : ℒ→ℒ defined over a complete lattice (ℒ, ≤ ) has a fixed point. 
Tarski proved the most general form of the theorem <cit.>:

    Let (ℒ, ≤) be a complete lattice and let f : ℒ→ℒ be an order-preserving (monotone) function with respect to ≤. Then the set of fixed points of f in ℒ forms a complete lattice under ≤.

 An earlier version was shown by Knaster and Tarski <cit.>, who established the result for the special case where ℒ is the lattice of subsets of a set (i.e. the power set lattice).
 
This is a classical theorem with broad applications. For example, in  formal semantics of programming languages and abstract interpretation,   the existence of fixed points can be exploited to guarantee well-defined semantics for a recursive algorithm <cit.>. In game theory, Tarski's theorem implies the existence of pure Nash equilibria in supermodular games <cit.>.
Surprisingly, it is not fully understood how efficiently Tarski fixed points can be found. 

Formally, for k,n ∈ℕ, let ℒ_n^k = {0, 1, …, n-1}^k be the k-dimensional grid of side length n.
Let ≤ be the binary relation where for vertices a = (a_1, …, a_k) ∈ℒ_n^k and b = (b_1, …, b_k) ∈ℒ_n^k, we have  a≤b if and only if a_i ≤ b_i for each i ∈ [k]. 
We consider the lattice (ℒ_n^k, ≤). A  function f :ℒ_n^k →ℒ_n^k is monotone if a≤b implies that f(a) ≤ f(b). 
Tarski's theorem  states that the set P of fixed points of f is non-empty and that the system (P, ≤) is itself a complete lattice <cit.>.
    
In this paper, we focus on the query model, where there is an unknown monotone function f:ℒ_n^k →ℒ_n^k. An algorithm has to probe a vertex v in order to learn the value of the function f(v). The  task is to find a fixed point of f by probing as few vertices as possible.  
The randomized query complexity  is the expected number of queries required to find a solution with a probability of at least 9/10 by the best algorithm [Any other constant greater than 1/2 would suffice.], where the expectation is taken over the coin tosses of the algorithm. 
  

There  are two main  algorithmic approaches for finding a Tarski fixed point. The  first approach is a divide-and-conquer method that yields an upper bound of O((logn)^⌈k+1/2⌉) for any fixed k due to  <cit.>, which improves  an algorithm of  <cit.>. 


The second  is a path-following method that initially queries the vertex 0⃗ = (0, …, 0) and proceeds by following the directional output of the function.
With each function application, at least one coordinate is incremented, which guarantees that  a fixed point is reached within O(nk) queries.

 <cit.> proved a randomized query complexity lower bound of Ω(log^2(n)) on the 2D grid of side length n, which implies the same lower bound for the k-dimensional grid of side length n when k is constant. This lower bound shows that the divide-and-conquer algorithm is optimal for dimensions k=2 and k=3. 

For dimension k ≥ 4, there is a growing gap between the best-known upper and lower bounds, since  
 the upper bound given by the divide-and-conquer algorithm has an exponential dependence on k. Meanwhile, the path-following method provides superior performance in high dimensions, such as the Boolean hypercube {0,1}^k, where it achieves an upper bound of O(k).





 §.§ Our Contributions



Let 
 TARSKI(n,k) denote the Tarski search problem on the k-dimensional grid of side length n. 

Let k,n ∈ℕ.
     Given oracle access to an unknown monotone function f : ℒ_n^k →ℒ_n^k, find a vertex x ∈ℒ_n^k with f(x) = x using as few queries as possible.
 

Our main result is the following:
 
There is a constant c > 0 such that for all k, n ∈ℕ, the  randomized query complexity of TARSKI(n,k) is at least c ·( k + k ·logn/logk).

The lower bound in <ref> is sharp for   constant n ≥ 2 and nearly optimal in the general case when k is large relative to n.

<ref> gives a characterization of Θ(k) for the randomized and deterministic query complexity on the Boolean hypercube {0,1}^k,  since the deterministic path-following method that iteratively applies the function starting from  vertex 0⃗ = (0, …, 0) finds a solution within O(k) queries. 
No lower bound better than Ω(1) was known for the Boolean hypercube.



    The randomized and deterministic query complexity of TARSKI(2,k) is Θ(k).


We obtain  <ref> by designing the following family of monotone functions.






















 


For each  a ∈ℒ_n^k,  
we define a function f^a : ℒ_n^k →ℒ_n^k coordinate by coordinate. That is, 
for each v =(v_1, …, v_k) ∈ℒ_n^k and i ∈ [k], let

    f^a_i(v) = 
            v_i - 1     if (v_i > a_i) and (v_j ≤ a_j for all j<i)
    
            v_i + 1     if (v_i < a_i) and (v_j ≥ a_j for all j<i)
    
            v_i     otherwise.

Let f^a(v) = (f^a_1(v), …, f^a_k(v)).
Define ℱ = {f^a | a ∈ℒ_n^k}.


The intuition is that the first digit that is too low and the first digit that is too high both get pushed towards their correct value.
An example of a function from Definition <ref>  is shown in Figure <ref>. 





For k=2, this construction is similar to the herringbone construction of <cit.>; however, our construction  does not induce a lower bound of  log^2(n) on the 2D grid since the shape of the path from (0,0) or (n-1,n-1) to the fixed point is too predictable. 

The real strength of our construction emerges  for large k, where the herringbone is not defined. Critically, a function f ∈ℱ has the property that f(v) differs from v in at most 2 dimensions for all v, no matter how large k is. This makes it difficult to derive information about more than a constant number of dimensions with a single query. The proof of <ref> makes this intuition precise. 





 §.§ Related Work
 





  
Tarski fixed points. Algorithms for the problem of finding Tarski fixed points on the k-dimensional grid of side length n have only recently been considered. <cit.> gave an O(log^k (n)) divide-and-conquer algorithm. <cit.> gave an O(log^2 (n)) algorithm for the 3D grid and used it to construct an O(log^2 ⌈ k/3 ⌉ (n)) algorithm for the k-dimensional grid of side length n. <cit.> extended their ideas to get an O(log^⌈ (k+1)/2 ⌉(n)) algorithm.

 <cit.> showed a lower bound of Ω(log^2(n)) for the 2D grid, implying the same lower bound for the k-dimensional grid of side length n. This bound is tight for k = 2 and k=3, but there is an exponential gap for larger k. They also showed that the problem is in both PLS and PPAD, which by the results of <cit.> implies it is in CLS.

<cit.> give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. This result  implies that the Tarski problem and the unique Tarski problem have the same query complexity.

Next we briefly summarize  query and communication complexity results for two problems representative for the classes PLS and PPAD, respectively. These problems are finding a local minimum and a Brouwer fixed point, respectively. In both cases, the existing lower bounds  also rely on hidden path constructions.



  
Brouwer fixed points.	In the  Brouwer search problem, we are given a function f : [0,1]^d → [0,1]^d that is L-Lipschitz, for some constant L > 1. The task is to find a fixed point of f using as few queries to f as possible. The existence of a fixed point is guaranteed by Brouwer's fixed point theorem.
 The query complexity of computing an -approximate Brouwer fixed point was studied in a series of papers starting with <cit.>,  which introduced a construction where  the function is induced by a  hidden walk. This was  later improved by <cit.> and <cit.>.




  
Local minima. In the local search problem, we are given  a graph G = (V,E) and a function f : V →ℝ. A vertex v is a local minimum if f(v) ≤ f(u) for all (u,v) ∈ E. An algorithm can probe a vertex v to learn its value f(v). The task is to find a vertex that is a local minimum using as few queries as possible. <cit.> obtains a lower bound  of Ω(2^k/2-o(k)) on the query complexity for the Boolean hypercube {0,1}^k by a random walk analysis.	
	Aldous' lower bound for the hypercube was later improved by 
	<cit.> to Ω(2^k/2/k^2) via a relational adversary method inspired from quantum computing.
	<cit.> further improved this lower bound to  Θ(2^k/2·√(k)) via a “clock”-based random walk construction.
	Meanwhile, <cit.> developed a deterministic divide-and-conquer algorithm.
	
	
	For the  k-dimensional grid [n]^k, 
	<cit.> used the relational adversary method  to show a randomized lower bound of Ω(n^k/2-1 / log n) for every constant k ≥ 3. <cit.> proved a randomized lower bound of Ω(n^k/2) for every constant k ≥ 4. 
	
	The work of <cit.> closed further gaps in the quantum setting as well as the randomized k=2 case.

For general graphs, <cit.> gave a quantum lower bound of Ω( √(s/Δ) / log(n) ), where n is the number of vertices of the graph, s is the separation number, and Δ the maximum degree.  
<cit.> improved this lower bound to Ω( √(s/Δ)) for randomized algorithms and also obtained a randomized lower bound of Ω(n^1.5/g), where g is the vertex congestion of the graph.
<cit.> also gave an upper bound of O((s +  Δ) ·log n), which was obtained by refining a  divide-and-conquer algorithm of <cit.>. 
	
	<cit.> gave lower bounds for Cayley graphs  as a function of the number of vertices and the diameter of the graph.
	<cit.> obtained upper bounds as a function of the genus of the graph.
	
   <cit.> studied the communication complexity of local search; this captures  distributed settings, where data is stored  on different computers.
	





















 




    
    








§ PROPERTIES OF THE FAMILY OF FUNCTIONS ℱ


In this section we show that each function in the family ℱ of Definition <ref> is monotone and has a unique fixed point.







For each a ∈ℒ_n^k, the function f^a from Definition <ref> is monotone.


    Consider two arbitrary vertices u,v ∈ℒ_n^k with u ≤ v.
    Suppose towards a contradiction that  f^a(u) ≤ f^a(v) does not hold.
    Then there exists an index i ∈ [k] such that f^a_i(u) > f^a_i(v).
    Since u ≤ v, we have u_i ≤ v_i, so at least one of  f^a_i(u) > u_i or  f^a_i(v) < v_i holds.
    
     
  Case 1: f^a_i(u) > u_i.
        By definition of f^a, we then have u_i < a_i and u_j ≥ a_j for all j<i.
        Since u ≤ v, we also have v_j ≥ a_j for all j<i.         Furthermore, we have  v_i = u_i, or v_i = u_i+1, or v_i ≥ u_i + 2. We consider a few sub-cases:
        
        	
  * (v_i = u_i). Then  f^a_i(v) = v_i + 1 = u_i + 1 = f^a_i(u).
        	
  * (v_i = u_i+1). Then  v_i ≤ a_i, so f^a_i(v) ≥ v_i = u_i + 1 = f^a_i(u).
        	
  * (v_i ≥ u_i + 2).
        Then f^a_i(v) ≥ v_i-1 ≥ u_i+1 = f^a_i(u).
        
                In each subcase (a-c), we have f^a_i(v) ≥ f^a_i(u). This is in  contradiction with  f^a_i(u) > f^a_i(v), thus case 1 cannot occur.

    
  Case 2: f^a_i(v) < v_i.
        By definition of f^a, we then have v_i > a_i and v_j ≤ a_j for all j<i.
        Since u ≤ v, we also have u_j ≤ a_j for all j<i.
        Furthermore, we have  u_i = v_i, or u_i = v_i - 1, or u_i ≤ v_i - 2. We consider a few sub-cases:
        
        	
  * (u_i = v_i). Then f^a_i(u) = u_i - 1 = v_i - 1 = f^a_i(v).
        	
  * (u_i = v_i - 1). Then u_i ≥ a_i, so f^a_i(u) ≤ u_i = v_i - 1 = f^a_i(v).
        	
  * (u_i ≤ v_i - 2). Then f^a_i(u) ≤ u_i + 1 ≤ v_i - 1 = f^a_i(v).       	
        
                In each subcase (a-c), we have f^a_i(u) ≤ f^a_i(v). This in contradiction with f^a_i(u) > f^a_i(v), thus case 2 cannot occur either.
    
    In both cases 1 and 2 we reached a contradiction, so the assumption that f^a(u) ≤ f^a(v)  does not hold must have been false. Thus f^a is monotone.


 
For each a ∈ℒ_n^k, the function f^a ∈ℱ has a unique fixed point at a.


By definition of f^a we have f^a(a) = a, so a is a fixed point of f^a.

Let v ≠ a. 
    Then there exists i ∈ [k] such that v_i  a_i. Let i be the minimum such index. We have two cases:
    

  * (v_i < a_i):
        Then f^a_i(v) = v_i + 1, so f^a(v) ≠ v.

  * (v_i > a_i):
        Then f^a_i(v) = v_i - 1, so f^a(v) ≠ v.

    In both cases v is not a fixed point, so a is the only fixed point of f^a.




§ LOWER BOUNDS





 §.§ Lower bound for the Boolean hypercube

Using the family of functions ℱ from <ref>, we can now  prove a randomized lower bound of Ω(k) for the Boolean hypercube {0,1}^k.


The randomized query complexity of TARSKI(2,k) is Ω(k).


We proceed by invoking Yao's lemma.
    Let  𝒰 be the uniform distribution over the set of functions ℱ. 
  Let 𝒜 be the deterministic algorithm with the smallest possible expected number of queries that succeeds with probability at least 4/5, where both the expected query count and the success probability are for input drawn from 𝒰.
    The algorithm 𝒜 exists since there is a finite number  of deterministic algorithms for this problem, so the minimum is well defined.
    
    Let D be the expected number of queries issued by 𝒜 on input drawn from 𝒰.
    Let R be the randomized query complexity of TARSKI(2,k); i.e. the expected number of queries required to succeed with probability at least 9/10.
    Then Yao's lemma (<cit.>, Theorem 3) yields 2R ≥ D. 
    Therefore it  suffices to lower bound D.  


    For each  t ∈ℕ, let
    
     
    
  * ℋ_t denote the history of queries and responses received at steps  1, …, t. 
    
    
  * ℐ_t = {i ∈ [k] |𝒜  a_i ℋ_t}.
    
  * v^t denote the t-th query submitted by 𝒜.


We prove by induction on t that ℐ_t is all the information that the algorithm 𝒜 has by the end of round t. Clearly ℐ_0 = ∅ since the algorithm has not made any queries so any input function is equally likely.
We assume the inductive hypothesis holds for t-1 and prove it for t.
We consider the indices where v^t has zeroes and divide in two cases; the analysis for indices where v^t has ones is symmetric. Initialize ℐ_t = ℐ_t-1. We explain in each case what new indices may enter ℐ_t.


  * There exists i ∈ [k] such that ( v^t_i = 0 and f^a_i(v^t) = 1 ). This implies three things:

    
  * a_i=1, so i is added to ℐ_t.
    
  * For all j < i such that v^t_j = 0, it must be the case that a_j = 0; otherwise, the bit at index j would have been corrected to a 1 instead of the bit at index i getting corrected. Therefore, each such j is added to ℐ_t.
    
  * The algorithm does not learn anything about the bits at locations  j > i with v^t_j = 0, since regardless of the value of a_j, we have f^a_j(v^t) = 0. No such j is added to ℐ_t, though some may have already been in ℐ_t-1.




  * There is no i ∈ [k] such that ( v^t_i = 0 and f^a_i(v^t) = 1 ). Then for all j ∈ [k] such that v_j^t = 0, it must have been the case that a_j = 0. Therefore, all such j are added to ℐ_t.


In either case (i) or (ii), the value of f^a_i(v^t) for indices i ∈ [k] with v^t_i = 0 gives 𝒜 no information about indices j ∈ [k] with v^t_j = 1, as the value of f^a(v^t) at such j depends only on other indices ℓ∈ [k] where v^t_ℓ = 1.

Thus for each index j ∈ [k], either j ∈ℐ_t (and so the algorithm 𝒜 knows the bit a_j with certainty) or the posterior for a_j remains the uniform distribution. This completes the inductive step.


   


Next we argue that the expected number of bits learned with each query is upper bounded by a constant, that is [|ℐ_t| - |ℐ_t-1| |ℋ_t-1] ≤ 4.

    
    


    



    For b ∈{0, 1}, let c_t(b) be the index of the bit where v_c_t(b)^t = b and f^a_c_t(b)(v^t) = 1-b, or c_t(b) = ∞ if no such index exists. Then define Δ_t(b) as:
    
    Δ_t(b) = { i | i ∉ℐ_t-1, v_i^t = b,  i ≤ c_t(b)} .

    In other words Δ_t(b) is precisely the set of indices i ∈ [k] added to ℐ_t (which were not in ℐ_t-1) with the property that v_i^t = b. 
    We therefore have 
    
    Δ_t(0) ∪Δ_t(1) = ℐ_t ∖ℐ_t-1 .


    The distribution of |Δ_t(b)| can be bounded effectively. For any C ∈ℕ, we have |Δ_t(b)| > C only if the first C indices i ∈ [k] with the property that both  i ∉ℐ_t-1 and  v_i^t = b are guessed correctly, i.e. a_i = b. 
   
   Therefore:
    
    [|Δ_t(b)|  > C |ℋ_t-1] ≤ 2^-C .

    We can bound the expected value of |Δ_t(b)| as:
    
    𝔼[|Δ_t(b)| |ℋ_t-1]    = ∑_C=0^∞[|Δ_t(b)| > C |ℋ_t-1] By Lemma <ref>
       ≤∑_C=0^∞ 2^-CBy  (<ref>)
       = 2 .


    Using (<ref>) and (<ref>), we get:
    
    𝔼[|ℐ_t| - |ℐ_t-1| |ℋ_t-1]    = 𝔼[|Δ_t(0)| |ℋ_t-1] + 𝔼[|Δ_t(1)| |ℋ_t-1] ≤ 2 + 2 = 4 .


    Since the upper bound of 4 applies for all histories ℋ_t-1, taking expectation over all possible histories gives:
    
    𝔼[|ℐ_t| - |ℐ_t-1|]  ≤ 4     ∀ t ∈ℕ .

    Since |ℐ_0| = 0, inequality (<ref>) implies  𝔼[|ℐ_t|] ≤ 4t.  Thus [|ℐ_t|] < 5t for all t ∈ℕ^*.
    
    Let T = k/100.
    Then by Markov's inequality applied to the random variable ℐ_T, we have
    
    [|ℐ_T| ≥ k] ≤[|ℐ_T|]/k < 5T/k = 1/20  .

When |ℐ_T| < k, algorithm 𝒜 makes an error with probability at least 1/2 since it would have to guess at least one bit of a. Since 𝒜 succeeds with probability at least 4/5, we must have |ℐ_T| = k with probability at least 3/5.
    
   
    Thus 𝒜 issues more than k/100 queries with probability at least 1 - 1/20 - 2/5 = 11/20.
    Therefore the expected number of queries issued by 𝒜 is D > (11/20) · (k/100) ∈Ω(k).




 §.§ Lower bound for the k-dimensional grid of side length n

In this section we  show the randomized lower bound of Ω(k) also holds for TARSKI(n,k). Afterwards, we prove the construction from <ref> also yields a lower bound of Ω(k logn/log(k)) for the k-dimensional grid of side length n.
 
   The randomized query complexity of TARSKI(n,k) is at least 
   the randomized query complexity of TARSKI(2,k).


    We show a reduction from TARSKI(2,k) to TARSKI(n,k).
    Let f^* : {0,1}^k →{0,1}^k be an arbitrary instance of TARSKI(2,k). As such, f^* is monotone.
    
    
    Let g : {0,1,…,n-1}^k →{0,1}^k be the clamp function, given by 
    
    g(v) = (g_1(v), …, g_k(v)),  g_i(v) = min(v_i, 1) ∀ i ∈ [k] .
 
    Then define f : {0,1,…,n-1}^k →{0,1,…,n-1}^k as f(v) = f^*(g(v)).

    To show that f is monotone, let u,v ∈{0,1,…,n-1}^k be arbitrary vertices with u ≤ v. Then g(u) ≤ g(v), so f(u) = f^*(g(u)) ≤ f^*(g(v)) = f(v) by monotonicity of f^*. Thus f is monotone and has a fixed point.

    Every vertex u ∈{0,1,…,n-1}^k ∖{0,1}^k is not a fixed point of f, since f(u) ∈{0,1}^k. Every fixed point u ∈{0,1}^k of f is also a fixed point of f^* since g(u) = u for all u ∈{0,1}^k. Therefore all fixed points of f are also fixed points of f^*.

    A query to f may be simulated using exactly one query to f^* since computing g does not require any knowledge of f^*.

    Therefore any algorithm that finds a fixed point of f can also be used to find a fixed point of f^* in the same number of queries. Therefore the randomized query complexity of TARSKI(n,k) is greater than or equal to the randomized query complexity of TARSKI(2,k).
 

Applying <ref> to <ref> directly gives the following corollary.
 
    The randomized query complexity of TARKSI(n,k) is Ω(k).


We also get the following lower bound.
 
    
     The randomized query complexity of TARSKI(n,k) is Ω(klog(n)/log(k)).
 
 
We proceed by invoking Yao's lemma.
    Let  𝒰 be the uniform distribution over the set of functions ℱ. 
  Let 𝒜 be the deterministic algorithm with the smallest possible expected number of queries that succeeds with probability at least 4/5, where both the expected query count and the success probability are for input drawn from 𝒰.
    The algorithm 𝒜 exists since there is a finite number  of deterministic algorithms for this problem, so the minimum is well defined.
    
    Let D be the expected number of queries issued by 𝒜 on input drawn from 𝒰.
    Let R be the randomized query complexity of TARSKI(n,k); i.e. the expected number of queries required to succeed with probability at least 9/10.
    Then Yao's lemma (<cit.>, Theorem 3) yields 2R ≥ D. 
    Therefore it  suffices to lower bound D. 
    

 
    
     For each vertex v ∈{0, …, n-1}^k, let Q_v be the set of possible outputs when plugging in v:
     
    Q_v = {f^a(v) | a ∈{0,1,…,n-1}^k} .

     
     We next bound |Q_v|.
     By the definition of f^a, the vertex f^a(v) differs from v in at most two coordinates: the first i ∈ [k] such that v_i > a_i (if any) and the first j ∈ [k] such that v_j < a_j (if any). Each of i and j have k+1 options, corresponding to the k dimensions and the possibility that no such dimension exists. Therefore
     
     
    |Q_v| ≤ (k+1)^2  .

     
     Recall that 𝒜 is defined to the best deterministic algorithm  that succeeds on 𝒰 with probability at least 4/5.
     Since 𝒰 is uniform over ℱ, there must exist at least (4/5) · n^k inputs on which 𝒜 outputs a fixed point.
     Then the decision tree of 𝒜 must have at least (4/5) · n^k leaves since all supported inputs have different and unique fixed points.
     Every node of this tree has at most (k+1)^2 children, since |Q_v| ≤ (k+1)^2 for all v by (<ref>).
     Therefore the average depth of the leaves is at least
     
    log_(k+1)^2((4/5)n^k ) - 1 = log_2((4/5) n^k)/log_2((k+1)^2) - 1 ≥k log_2 (n) -1/2log_2 (k) + 2 - 1 ∈Ω(k log n/log k)  .




Then on input distribution 𝒰, algorithm 𝒜 issues an expected number of queries of D ∈Ω(k log n/log k).
     
     Thus the randomized query complexity of TARSKI(n,k) is Ω(k log n/log k) as required.
 

The proof of <ref> follows from <ref> and <ref>.


The randomized query complexity of TARSKI(n,k) is 
 Ω(k) by <ref> and 
 Ω(k logn/log(k)) by <ref>.
This implies a lower bound of Ω( k + k logn/log(k)) as required.




§ UPPER BOUND FOR THE FAMILY OF FUNCTIONS ℱ


It may seem that the family of instances ℱ from <ref> should in fact yield a lower bound of Ω(k logn). Intuitively, k logn may be achievable since the only feedback an algorithm receives with each query on an input from ℱ is whether the query is too high or too low on roughly two coordinates. 
However, this intuition turns out to be incorrect when n is close to k.
The next proposition shows that the family of functions ℱ cannot yield a lower bound of Ω(k logn) for all k and n.


    There is a deterministic O(k + n)-query algorithm for TARSKI(n, k) on the set of functions ℱ.



    For each coordinate i ∈ [k] and each query index t, let x^t_i and y^t_i be the minimum and maximum possible values of a_i given the first t queries the algorithm makes. For example, x^0_i = 0 and y^0_i = n-1 for all i ∈ [k], and the algorithm finishes in T queries if x^T_i = y^T_i for all i ∈ [k].

    If the algorithm has not finished by its (t+1)-th query, it queries the vertex with coordinates:
    
    v^t+1_i = 
                x^t_i    if x^t_i = y^t_i
    
                x^t_i + 1    otherwise


    There are two possible outcomes from each such query:
    
        
  * Some coordinate j satisfies f^a_j(v^t+1) = v^t+1_j - 1. This immediately identifies a_j = x^t_j, as a_j ≥ x^t_j and a_j < x^t_j + 1. Since there are only k coordinates to learn, this case can occur for at most k queries before the algorithm terminates.
        
  * No coordinate j satisfies f^a_j(v^t+1) = v^t+1_j - 1. Then, for each i such that x^t_i < y^t_i, the possibility of a_i = x^t_i is ruled out. Since each coordinate only has n possible values, this case can occur for at most n queries before the algorithm terminates.
    

    Therefore, this algorithm terminates within O(k+n) queries.




§ DISCUSSION


It would be interesting to characterize the query complexity of the Tarski search problem as a function of the grid side-length n and dimension k.



§ ACKNOWLEDGEMENTS

We are grateful to Davin Choo and Kristoffer Arnsfelt Hansen for useful discussions.

alpha








§ A FOLK LEMMA



    
Let X be a random variable that takes values in ℕ. Then 
[X] = ∑_C = 0^∞ [X > C] .



    By the definition of [X]:
    
    [X]    = ∑_n=0^∞ n · [X = n]  = ∑_n=0^∞∑_C=1^n  [X = n]  = ∑_C=1^∞∑_n=C^∞ [X = n] = ∑_C=1^∞ [X ≥ C] = ∑_C=0^∞ [X > C]  .



