Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform students transfer along efficient refutation translations

Proved
StudentTeacher976.Adaptivity.uniform_refutation_translation_transfer

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptivitycomputational-complexitystudent-teacher

Let PPP and QQQ be refutable presentations of the same search relation at hierarchy level iii. Let rrr be any round function and qqq a polynomial-time query function. Suppose a function ψ(x,y,z)\psi(x,y,z)ψ(x,y,z) is computable in FPΣip\mathrm{FP}^{\Sigma_i^p}FPΣip​ on the encoded triple, and for every PPP-certificate zzz of its prescribed length,

∣ψ(x,y,z)∣=bQ(∣x∣),Q(x,y,ψ(x,y,z))⟹P(x,y,z).|\psi(x,y,z)|=b_Q(|x|),\qquad Q(x,y,\psi(x,y,z))\Longrightarrow P(x,y,z).∣ψ(x,y,z)∣=bQ​(∣x∣),Q(x,y,ψ(x,y,z))⟹P(x,y,z).

Here P(x,y,z)P(x,y,z)P(x,y,z) and Q(x,y,w)Q(x,y,w)Q(x,y,w) denote the presentations' Boolean success tests, not the underlying binary relation. Then

Q has a uniform winning (r,q) student⟹P has a uniform winning (r,q) student.Q\text{ has a uniform winning }(r,q)\text{ student} \Longrightarrow P\text{ has a uniform winning }(r,q)\text{ student}.Q has a uniform winning (r,q) student⟹P has a uniform winning (r,q) student.

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 sorry
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me