Tarski instances and solutions
DefinitionTarskiBootstrap_Dimensional_Supplement_TarskiStaradversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points
A Tarski instance is a pair of a monotone map and a monotone sign function , monotone meaning whenever . The oracle at returns . A point is a solution if
No bounded-increment restriction is imposed on . This is the intermediate problem through which the hidden-sign construction passes.
Formalization Note Signs are Mathlib's SignType, ordered .
Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Grid
namespace TarskiBootstrap.Dimensional.Supplement
/-- Definition 2.3, PDF/printed p. 6: a `Tarski*(n, k)` instance is a monotone
`f : [n]^k → [n]^k` together with a monotone sign function `σ : [n]^k → {-1, 0, 1}`
(`σ(x) ≤ σ(y)` whenever `x ⪯ y`); no bounded-increment condition is imposed. -/
def IsTarskiStarInstance {n k : ℕ+} (f : Grid n k → Grid n k)
(σ : Grid n k → SignType) : Prop :=
Monotone f ∧ Monotone σ
/-- Definition 2.3: `x` solves the `Tarski*` instance `(f, σ)` iff
`x ⪯ f(x) ∧ σ(x) ≥ 0` or `x ⪰ f(x) ∧ σ(x) ≤ 0`. -/
def IsTarskiStarSolution {n k : ℕ+} (f : Grid n k → Grid n k)
(σ : Grid n k → SignType) (x : Grid n k) : Prop :=
(x ≤ f x ∧ 0 ≤ σ x) ∨ (f x ≤ x ∧ σ x ≤ 0)
end TarskiBootstrap.Dimensional.Supplement
Source
Li, Ma, Yang and Zhao, Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points, STOC 2027 submission #6 (2026), frozen preprint, Definition 2.3, PDF/printed p. 6, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.