claimroutine

Header parsing and list setup cost

Header parsing and list setup take poly⁡(p)=O(Tp)\operatorname{poly}(p)=O(Tp) time
shows setup cost is negligible
Claim·§6.2 A layout on which the parallel layers apply·inside lemCost and accuracy of synthetic transform

Statement (paper)

The header T\mathcal T has O(p)O(p) bits, and the layout lists have binary length polynomial in pp. Parsing the header and generating these lists by elementary integer arithmetic take poly⁡(p)=O(Tp)\operatorname{poly}(p)=O(Tp) time, since the fixed comparison bands give T≥r≥2(ar/bd)p1−ϵT\geq r\geq2^{(a_r/b_d)p^{1-\epsilon}}, uniformly over the permitted d,rd,r, so that TT dominates every fixed power of pp.

In plain English

The header T\mathcal T has O(p)O(p) bits, and the layout lists built from it have length polynomial in pp. Parsing the header and generating these lists takes poly⁡(p)=O(Tp)\operatorname{poly}(p)=O(Tp) time, because T≥r≥2(ar/bd)p1−ϵT\geq r\geq 2^{(a_r/b_d)p^{1-\epsilon}} grows faster than any fixed power of pp.

Why it's here

This step shows that the setup work (reading the header and building the layout lists) is negligible next to the O(Tp)O(Tp) time budget of the parent lemma. The key point is that the comparison bands force rr, and hence TT, to be superpolynomial in pp uniformly over the permitted d,rd,r, so any polynomial in pp is absorbed into O(Tp)O(Tp).
Classified routine:
Routine bookkeeping: polynomial-time header parsing is absorbed into the O(Tp) budget because the parameter bands make T at least 2^{c p^{1-ε}}, which is superpolynomial in p.

Uses

Nothing else in the paper

Used by

Nothing in the paper

Sources

PaperOpen
Section
§6.2 A layout on which the parallel layers apply
Page
—
Label
—
Line
sections/06-transforms.tex:291
Leannot aligned

Phase 2 aligns this node to a Lean declaration.