We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $\Omega((\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 $\Omega((\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.
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 t...
Tong-Yang Li, Wei-Ran Ma, Zi-Yi Yang et al.· 1 citation
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 co...
Tong-Yang Li, Wei-Ran Ma, Zi-Yi Yang et al.· 3 citations· ⚡1
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 $\Omega((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very r...
Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer $p\ge3$, finding an $\eps$-stationary point requires $\Omega_p(\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\infty$ objectives with i...
Hai-Han Zhang, Wen-Dao Wu, Fang-Qing Zhang et al.· 0 citations
Let $R_r(k)$ denote the diagonal $r$-colour Ramsey number. We prove that there exist absolute constants $c,K>0$ such that $R_r(k)\le r^{rk}\exp\!\left(-c\frac{k}{r\log^2(2r)}\right)$ for every $r\ge2$ and every $k\ge Kr^2\log^6(2r)$. This improves the exponential saving in a recent bound of Yang and Mao by a factor of...
We prove that for every integer $d \geq 3$, there exists $\alpha<1$ such that the maximum dimension of an $n$-element poset containing no standard example of order $d$ as an induced subposet is $\mathcal{O}_d(n^\alpha)$. For $d=3$, we obtain an upper bound $\mathcal{O}(n^{2/3}\log n)$, while we also construct a family...
Jȩdrzej Hodor, P. Micek, William T. Trotter· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
