Dimension Amplification for Tarski Fixed-Point Query Lower Bounds

Boyu Liu, Zihe Wang

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 e…