claimroutine

Depth-first traversal gives polynomial space

Claim·§D.4.7 Time and space bounds·inside thmSubexponential Boolean tensor network contraction

Statement (paper)

The recursive contraction algorithm can be carried out by a depth-first traversal using only

(s+\mathcal L)^{O(1)}

bits of space: the recursion has

O_C(\log\lambda)

stack levels, each call stores data of size polynomial in

s+\mathcal L

, and the original and newly constructed entry routines use polynomial space. Hence the contraction in

\mathcal B_{P_0,\ell}

is obtained from the base coordinates in

\mathcal A_{P_0}

within

(s+\mathcal L)^{O(1)}

bits of space.

In plain English

The recursive contraction algorithm can be run as a depth-first traversal using only

(s+\mathcal L)^{O(1)}

bits of space, because the recursion has

O_C(\log\lambda)

levels, each call stores polynomially sized data, and the entry routines use polynomial space. Hence the contraction in

\mathcal B_{P_0,\ell}

is obtained from the base coordinates in

\mathcal A_{P_0}

in polynomial space.

Why it's here

This claim gives the space half of the theorem's bound. The time bound comes from the recursion's branching, but a depth-first traversal keeps only one root-to-leaf path in memory, so the logarithmic depth times polynomial per-call storage stays polynomial. The tapered Hermite recovery step from the lemma runs in polynomial space, so the recovery done at each level adds only polynomial space.

Classified routine:

This is the standard space accounting for a depth-first recursive algorithm: logarithmic recursion depth times polynomial storage per stack frame, with polynomial-space subroutines such as the tapered Hermite recovery lemma, gives polynomial space. It is bookkeeping, not a new idea.

Uses

lemTapered Hermite recovery of F(0)

Used by

Nothing in the paper

Sources

PaperOpen

Section: §D.4.7 Time and space bounds
Page: —
Label: —
Line: quantitative-contraction.tex:603

Leannot aligned

Phase 2 aligns this node to a Lean declaration.