1Cademy - The stated fast-contraction theorem and its input requirements

Learn Before

Contracting a Boolean tensor network by summing shared wire assignments
Storing truncated polynomials with coefficients modulo a power of two
Reading the parameter bounds as asymptotic statements

Concept

The stated fast-contraction theorem and its input requirements

The manuscript asserts a fast contraction theorem for fixed constants C,A,b. With size parameter s>=2 and description length L, require: a bipartite network with at most Cs wires, maximum degree at most ceil(s^(9/10)), polynomially many vertices, and entries in B_(P0,ell) with 1<=P0,ell<=Cs. Each requested entry must be computable uniformly in time (s+L)^b 2^(A s^(9/10)) and space (s+L)^b. The stated contraction bound is (s+L)^{O(1)} 2^{O(s/sqrt(log s))} time and polynomial space. This is the theorem contract, NOT its proof. The recursive contraction proof remains outside this encoding-only learning-path stage; subsequent speed bounds are conditional on that theorem.

Updated 2026-11-08

Contributors are:

Who are from:

References