The composite problem
DefinitionTarskiBootstrap_Dimensional_Supplement_Compositeadversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points
Fix , and . The composite problem has index set . Its domain (equation (2.13)) consists of the strings on this index set such that, for every , the block is an input of , and the vector of inner answers is an instance. The composite function (2.12) applies to that vector. For signs and maps , the oracle of the input is
This is the abstract problem that the staircase construction embeds into a grid.
Formalization Note Positions are encoded by Fin m.
Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_HiddenSign
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_OrderedSearch
namespace TarskiBootstrap.Dimensional.Supplement
/-- The oracle `h(r, z) = H_{s_r}(f_r)(z) = (f_r(z), σ_{s_r}^{f_r}(z))` of the composite
input `(s, f)`, on the index set `{1, …, m} × [n]^k` of (2.11) (positions encoded by
`Fin m`), PDF/printed pp. 19, 21. -/
noncomputable def compositeOracle {n k : ℕ+} {m : ℕ+} (A : Set (Grid n k))
(s : Fin (m : ℕ) → SignType) (f : Fin (m : ℕ) → Grid n k → Grid n k) :
Fin (m : ℕ) × Grid n k → Grid n k × SignType :=
fun p => hiddenSignOracle A (s p.1) (f p.1) p.2
/-- The domain (2.13), p. 8, of `OS_m ∘ (Tarski^H(n,k)|F′, …, Tarski^H(n,k)|F′)`:
strings on `{1, …, m} × [n]^k` whose `r`-th block is an input of `Tarski^H|F′` for
every `r`, and whose vector of inner answers is an `OS_m` instance. -/
noncomputable def compositeDomain {n k : ℕ+} (A : Set (Grid n k))
(F : Set (Grid n k → Grid n k)) (m : ℕ+) :
Set (Fin (m : ℕ) × Grid n k → Grid n k × SignType) :=
{x | (∀ r, (fun z => x (r, z)) ∈ hiddenSignFamily A F) ∧
∃ i, (fun r => tarskiHAnswer (fun z => x (r, z))) = osInstance m i}
/-- The composite function (2.12), p. 8: `OS_m` applied to the vector of inner
`Tarski^H` answers. -/
noncomputable def compositeAnswer {n k : ℕ+} (m : ℕ+)
(x : Fin (m : ℕ) × Grid n k → Grid n k × SignType) : Fin (m : ℕ) :=
osOutput m (fun r => tarskiHAnswer (fun z => x (r, z)))
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.9, equations (2.11)–(2.13), PDF/printed p. 8; §4.2–4.3, pp. 19, 21, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.