Assembly of the word-RAM recursion from its local kernels
ProvedVWZClique.IntegerRAM.NativeFrame.realizes_of_implementedclique-countinggraph-algorithmsword-ram
Suppose two fixed families of word-RAM subroutines satisfy the local recursive contracts for the weighted nine-vertex pattern. One evaluates the projected branch and the other prepares a recursive child. Assume the contracts’ instruction and address bounds. Then for every sufficiently large fixed , one word-RAM program takes an ordinary graph adjacency input, constructs its weighted nine-part instance, evaluates the full recursive plan, and writes that plan's exact integer answer to the output cell. Its instruction count is bounded by the abstract recursive work times a fixed polynomial in the logarithm of the padded domain size.
Preamble
import Definitions.Def_VWZClique_NativeCliqueCompiler
Formal statement
theorem VWZClique.IntegerRAM.NativeFrame.realizes_of_implemented {mm : ℕ → ℕ} {T U A : ℕ}
(impl : VWZClique.IntegerRAM.NativeFrame.Implemented mm T U A) :
VWZClique.NativeTraversal.Realizes mm T U A := by sorrySource
V. Vassilevska Williams and O. Zamir, The k-Clique hypothesis is dead, for good, §3 (weighted recursion), §3.4 (grouping) and Appendix A, pp. 21–22 (word-RAM implementation). This is the assembly lemma connecting the local kernels to the recursion. https://zamir.prof/kclq.pdf