Query complexity for finding fixed points grows in six dimensions
The Six-Dimensional Tarski Problem is $Ω(\log^3 n)$-Hard
Computational Complexity
Summary
The paper looks at how hard it is for a computer to find a special point where a given function doesn't change its value, called a fixed point, when the function works in multiple dimensions. The authors improve the understanding of how many questions (queries) a program must ask to find this fixed point, especially when there are six dimensions involved. They showed that in six dimensions, the complexity is roughly proportional to the cube of the logarithm of the size of the input, which means it takes more queries than was previously proven. This helps clarify the difficulty of solving these kinds of problems deterministically.
What this means in practice
- •For algorithm designers: Set realistic expectations on the minimum number of queries needed for deterministic algorithms that find fixed points in six-dimensional monotone settings.
- •For complexity theorists: Use the improved lower bound to guide the search for optimal algorithms or prove hardness in higher-dimensional problems involving fixed points.
A theory result. No direct application yet.
Authors
Kristóf Zólomy
Abstract
We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $Ω((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})$. In particular, we obtain the optimal $Θ((\log n)^3)$ deterministic query complexity in six dimensions.