Proof of Theorem 1 — is monotone in
ProvedStretchDepth.testOf_monoblack-box-reductionscomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomnessquery-complexity
For partial assignments and every ,
Assigning more values leaves fewer completions, hence fewer reachable outputs. In the proof this gives .
Differences from the source:
- encoding: T_tau(y) <= T_sigma(y) as bits → T_tau(y) = true implies T_sigma(y) = true; reason: the same statement on {0, 1}
Preamble
import Definitions.Def_StretchDepth_testOf
Formal statement
namespace StretchDepth
/-- **Proof of Theorem 1: `T_ρ` is monotone.**
Korten, *Tight Depth Lower Bounds for Stretch Amplification*, STOC 2027 submission (manuscript
sha256 32d209e2…), proof of Theorem 1, p.21: "Note that for any pair of partial assignments τ ⊇ σ, we must have
Tτ(y) ≤ Tσ(y) for every y". -/
theorem testOf_mono {n N m M : ℕ} (H : Bits m → RoundTree n N M) (τ σ : PartialAssign n N)
(hτσ : ExtendsPartial τ σ) (y : Bits M) (hy : testOf H τ y = true) :
testOf H σ y = true := by sorry
end StretchDepth
Source
Korten, Tight Depth Lower Bounds for Stretch Amplification, STOC 2027 submission (manuscript sha256 32d209e2…), proof of Theorem 1, p.21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.