Manuscript XXII-D@1 · XXII-D.tex · theorem · 17889d18

Theorem: Conditional propagation-depth lower bound

Locality and resource bounds require a model › A finite-network lower bound · lines 1119–1151 · proof included or linked

XXII-D@1#thm:depth, XXII-D@1#eq:depth-lower

Back to manuscript

Under Specification spec:bounded-step, suppose

d_{⋄} (Λ_{n, ζ}, id_{M}) < 1 - \frac{1}{d ^{2}} .

Let $r = ∥ x ∥_{2}$ be the target spatial displacement and suppose $∥ x_{n, ζ} - x ∥_{2} \leq δ_{n}$ . Then

N_{n} \geq ⌈ \frac{( r - δ _{n} ) _{+}}{a _{n}} ⌉ .

If each round has calibrated duration $h_{n} > 0$ , measured from the declared source-input cut, then that execution duration is at least the right side of (eq:depth-lower) multiplied by $h_{n}$ .

Proof. Lemma lem:no-path forces a dependency path. If it contains $k$ spatially nonzero hops, the triangle inequality gives

∥ x_{n, ζ} ∥_{2} \leq k a_{n} \leq N_{n} a_{n} .

The reverse triangle inequality gives $∥ x_{n, ζ} ∥_{2} \geq (r - δ_{n})_{+}$ . This proves the integer bound. The duration statement is the declared round-duration convention.

Displayed formulas in this passage

unlabeled · line 1122
$d_{⋄} (Λ_{n, ζ}, id_{M}) < 1 - \frac{1}{d ^{2}} .$
XXII-D@1#eq:depth-lower · line 1128
$N_{n} \geq ⌈ \frac{( r - δ _{n} ) _{+}}{a _{n}} ⌉ .$
unlabeled · line 1144
$∥ x_{n, ζ} ∥_{2} \leq k a_{n} \leq N_{n} a_{n} .$

Theorem: Conditional propagation-depth lower bound

Displayed formulas in this passage

Nearby in this section