Uniform students transfer along efficient refutation translations
ProvedStudentTeacher976.Adaptivity.uniform_refutation_translation_transferadaptivitycomputational-complexitystudent-teacher
Let and be refutable presentations of the same search relation at hierarchy level . Let be any round function and a polynomial-time query function. Suppose a function is computable in on the encoded triple, and for every -certificate of its prescribed length,
Here and denote the presentations' Boolean success tests, not the underlying binary relation. Then
The translated student processes only earlier reply batches, so it preserves the round and parallel-query budgets exactly. This interface makes the computational requirement on a change of presentation explicit.
Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game set_option autoImplicit false open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
Formal statement
theorem StudentTeacher976.Adaptivity.uniform_refutation_translation_transfer {i : ℕ} {R : SearchRelation} (P Q : RefutablePresentation i R)
(r q : ℕ → ℕ) (hq : PolyTimeLength q) (ψ : Word → Word → Word → Word)
(heff : ∃ F : Word → Word,InFP i F ∧ ∀ x y z,F (tup [x,y,z])=ψ x y z)
(hlen : ∀ x y z : Word,z.length=P.refutationLength.eval x.length →
(ψ x y z).length=Q.refutationLength.eval x.length)
(htest : ∀ x y z : Word,z.length=P.refutationLength.eval x.length →
Q.test x y (ψ x y z) → P.test x y z)
(g : Student) (hg : UniformStudent i g) (hshape : StudentShape Q r q g)
(hwin : StudentWins Q r q g) :
∃ f : Student,UniformStudent i f ∧ StudentShape P r q f ∧ StudentWins P r q f := by sorrySource
Ježil–Tsintsilidas, Parallelism and Adaptivity in Student-Teacher Witnessing, STOC 2027 submission #976, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/976.pdf, Definition 1.2, p.7; causal composition interface for the published uniform-student model.