Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The fixed-presentation adaptivity separation excludes advice students

Proved
StudentTeacher976.Adaptivity.presented_adaptivity_separation_with_advice

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

adaptivitycomputational-complexitypolynomial-advicestudent-teacher

Fix i≥0i\ge0i≥0 and assume Σi+1p⊈Δi+1p/poly\Sigma_{i+1}^p\not\subseteq\Delta_{i+1}^p/\mathrm{poly}Σi+1p​⊆Δi+1p​/poly. Let rrr and qqq satisfy the admissibility conditions of Theorem 1.4, including monotonicity, unboundedness and the positive sublinear bound for rrr.

There exist a total search relation RRR and one faithful refutation presentation PPP of RRR such that:

  1. A uniform FPΣip\mathrm{FP}^{\Sigma_i^p}FPΣip​ student wins with this presentation in r(m)+1r(m)+1r(m)+1 rounds and one query per round.
  2. No student realized by FPΣip/poly\mathrm{FP}^{\Sigma_i^p}/\mathrm{poly}FPΣip​/poly wins with this same presentation in r(m)r(m)r(m) rounds and q(m)q(m)q(m) simultaneous queries per round.

Writing Wa,b(P)W_{a,b}(P)Wa,b​(P) for uniform solvability of the fixed presentation, and Wa,badv(P)W^{\mathrm{adv}}_{a,b}(P)Wa,badv​(P) for solvability with polynomial advice,

∃R ∃P presenting R,Wr+1,1(P)  ∧  ¬Wr,qadv(P).\exists R\,\exists P\text{ presenting }R,\qquad W_{r+1,1}(P)\;\wedge\;\neg W^{\mathrm{adv}}_{r,q}(P).∃R∃P presenting R,Wr+1,1​(P)∧¬Wr,qadv​(P).

Advice is shared by all student inputs of each encoded input length and need not be computable. The result strengthens the lower bound for a fixed presentation to exclude advised students. Both resource budgets and the refutation presentation are kept fixed in the comparison. It does not assert noninclusion between classes that permit arbitrary replacement presentations of the underlying relation.

Preamble
import Definitions.Def_StudentTeacher976_Adaptivity_Game
import Definitions.Def_StudentTeacher976_Adaptivity_AdviceSelectors
set_option autoImplicit false
open QAdvFew.PoQOracle StudentTeacher976.Adaptivity
open AdviceComputations (InFPAdvice)
Formal statement
theorem StudentTeacher976.Adaptivity.presented_adaptivity_separation_with_advice (i : ℕ) (hardness : ¬StudentTeacher976.Adaptivity.Sigma (i+1)⊆DeltaPoly i)
    (r q : ℕ → ℕ) (hr : AdmissibleRounds r) (hq : AdmissibleQueries q) :
    ∃ (R : SearchRelation) (P : RefutablePresentation i R),
      (∃ g : Student,UniformStudent i g ∧
        StudentShape P (fun m => r m+1) (fun _ => 1) g ∧
        StudentWins P (fun m => r m+1) (fun _ => 1) g) ∧
      ¬∃ g : Student,
        (∃ F : Word → Word,InFPAdvice i F ∧ ∀ (x : Word) (t : ℕ) (H : List (List Word)),
          F (tup [x,List.replicate (t+1) true,tup (H.map tup)])=tup (g x t H)) ∧
        StudentShape P r q g ∧ StudentWins P r q g := by sorry
Source
Strengthening of the fixed-presentation argument in 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, Theorem 1.4 p.7, proof §3.1 pp.19–21, Claim 3.1 p.20, Appendix A pp.39–40. The lower student is allowed polynomial advice, which is incorporated in the decision algorithm’s polynomial advice.

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