Ordered search and
DefinitionTarskiBootstrap_Dimensional_Supplement_OrderedSearchadversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points
For a positive integer and a hidden position , the ordered search instance is the string given by
The problem asks for the hidden position given oracle access to . Its spectral adversary value is the value (2.8) of the output map on the instance strings.
These objects enter the statement of the logarithmic bootstrapping theorem, whose amplification factor is .
Formalization Note Positions are encoded by Fin m with the same order. The output map returns the hidden position of an instance string (instances are pairwise distinct) and an arbitrary fixed position on other strings, which never enter.
Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_SpectralAdversary
namespace TarskiBootstrap.Dimensional.Supplement
/-- Definition 2.2, PDF/printed p. 6: the ordered search instance with hidden position
`i`, `f_i(j) = 1` for `j < i`, `0` for `j = i`, `-1` for `j > i`. Positions
`1, …, m` are encoded as `Fin m = {0, …, m-1}` with the same order. -/
def osInstance (m : ℕ+) (i : Fin (m : ℕ)) : Fin (m : ℕ) → SignType :=
fun j => if j < i then 1 else if j = i then 0 else -1
/-- The output of `OS_m`: the hidden position of an ordered search instance. Off the
instances (never used) it returns the first position. -/
noncomputable def osOutput (m : ℕ+) (t : Fin (m : ℕ) → SignType) : Fin (m : ℕ) := by
classical
exact if h : ∃ i, osInstance m i = t then h.choose else ⟨0, m.pos⟩
/-- `SA(OS_m)`, the spectral adversary value (2.8) of ordered search on its `m`
instances. -/
noncomputable def osSA (m : ℕ+) : ℝ :=
spectralAdversary (Set.range (osInstance m)) (osOutput m)
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.2, PDF/printed p. 6; equation (2.8), p. 7, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.