CS Paper Radar

Dimension Amplification for Tarski Fixed-Point Query Lower Bounds

Boyu Liu, Zihe Wang

cs.CC ·submitted 2026-10-05 00:42 UTC · v1
theory

Abstract

We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $Ω((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uniqueness, and adds a logarithmic factor to the lower bound. Iteration gives $Ω((\log N)^{r+2})$ queries in dimension $(7\cdot4^r-1)/3$, for every fixed nonnegative integer $r$, with an implicit constant that may depend on $r$. Consequently, no finite logarithmic exponent bounds the query complexity in all fixed dimensions.

Comment
22 pages

Closest papers

Nearest neighbours by meaning across the whole index.

The Six-Dimensional Tarski Problem is $Ω(\log^3 n)$-Hard

cs.CC ·2026-10-15 ·Kristóf Zólomy
theory similarity 0.78
Abstract · 17 pages, 7 figures

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.

0.22

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

cs.CC quant-phcs.DS ·2026-10-12 ·Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao
theory similarity 0.73
Abstract · 29 pages, 4 figures

The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $Ω(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$, there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$, and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{Ω(\log k)}$ for exponentially wide grids, where $n=2^{Θ(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.

0.30

Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid

cs.CC quant-phcs.DS ·2026-09-03 ·Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao
theory similarity 0.71
Abstract · 35 pages, 5 figures

The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and its algorithmic variants have found broad applications in areas such as economics, game theory, and programming languages. While the query complexity of finding a Tarski fixed point has been extensively studied in classical models, comparatively little is known in the quantum setting. We prove an $Ω(k\log n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]^k$, using the nonnegative spectral adversary method. In the two extremal regimes $n = 2$ and $k = 1$, our quantum lower bound matches the previous classical lower bounds $Ω(k)$ and $Ω(\log n)$, respectively. For $n, k\geq 2$, our bound improves the best previous classical lower bound when $n < k$ and is within a factor of $\log n / \log k$ compared to the known classical lower bound when $n \geq k$. To construct the adversary matrix, we develop the Tree--Filtration Adversary Method. Besides yielding our lower bound, the method offers a more transparent combinatorial interpretation of the nonnegative spectral adversary method. When the hard instances of a problem admit a tree-like organization and suggest an intuition analogous to classical decision-tree lower bounds, our method provide a promising approach to establishing quantum complexity lower bounds.

0.54

Tarski Fixed Points in Quasi-FPT Queries

cs.CC cs.DS ·2026-10-05 ·Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis
publishedtheoryhighly cited similarity 0.70
Abstract

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{Ω(\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$, \[ Ω\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)^{Θ(\log k )}$. In particular, we obtain the first super-polynomial query lower bound for this problem.

0.59

Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$

cs.CC ·2026-10-27 ·Eric Binnendyk
theory similarity 0.67
Abstract

It is known that the problem of recognizing the existence of a unit-distance realization in $\mathbb{Z}^d$ for a graph $G$ is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of $2^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(n^{2/3})}$ in $\mathbb{Z}^3$, and give an upper bound of $2^{O(n^{(d-1)/d} (\log n)^2)}$ for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of $\tildeΩ(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.

0.27

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.64
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Local Modifications of Nearest-Neighbor and Min-Plus Representations

cs.CC cs.DM ·2026-11-10 ·Liliia Redina
theory similarity 0.62
Abstract · 19 pages, 2 figures

We study how changing a Boolean-valued function at $d$ inputs affects the size and precision of its exact representations. Starting from a representation of size $m$, we prove four bounds, two for nearest-neighbor (NN) representations and two for integer min-plus representations. (i) For NN representations on a finite subset of $\mathbb{R}^n$ with $n\ge2$, at most $m+2d$ anchors suffice. The coefficient $2$ is optimal: on a three-point domain, changing one value can increase the minimum number of anchors from one to three. (ii) For NN representations on the Boolean cube with rational anchors, let $R$ be the maximum original coordinate bit length, and let $Δ$ be the maximum bit length of the least common denominator of any one original anchor's coordinates. We construct a representation with at most $m+3d$ anchors on a common dyadic grid and coordinate bit length $O(R+Δ+\log(n+1))$. (iii) For integer min-plus representations on the Boolean cube, we give a construction that keeps the original $m$ forms and their labels and adds at most $d$ new forms. Its maximum weight is at most $W+2n$, where $W$ is the largest absolute original coefficient, including constant terms. (iv) For integer min-plus representations on a finite rational domain $X\subset\mathbb{Q}^n$, at most $m+2d$ forms suffice. Their maximum weight is polynomially bounded in $m,d,W,n,|X|$, the coordinate bound, and the common denominator of $X$. The coefficient $2$ is again optimal: on a three-point domain, changing one value can increase the minimum number of forms from one to three. These bounds imply stability under polynomially many changes on the cube for polynomial-size representations, including those with polynomially bounded NN coordinate bit length or min-plus weight.

0.27

Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set

cs.DS cs.CC ·2026-10-26 ·Zhao Song
similarity 0.61
Abstract

We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrowα(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.

0.23