Compiling the recursive weighted clique-counting program from its projected contraction
ProvedVWZClique.IntegerRAM.NativeArena.compiled_of_projectionclique-countingfine-grained-complexityword-ram
Assume the projected contraction satisfies the fixed word-RAM program and cost bounds in ProjectionKernel, with square multiplication charge and fixed parameter . Then the weighted clique-counting recursion admits an implementation using that projection kernel, a fixed procedure for constructing its child instances, and a uniform word-width bound. The setup and per-child coefficients in the recursion cost model may both be taken to be .
Preamble
import Mathlib import Definitions.Def_VWZClique_NativeProjectionContract import Definitions.Def_VWZClique_NativeCliqueCompiler
Formal statement
theorem VWZClique.IntegerRAM.NativeArena.compiled_of_projection
{mm : ℕ → ℕ} {T : ℕ} (pk : VWZClique.IntegerRAM.NativeArena.ProjectionKernel mm T) :
Nonempty (VWZClique.IntegerRAM.NativeFrame.Implemented mm T 1 1) := by sorrySource
V. Vassilevska Williams and O. Zamir, “The k-Clique hypothesis is dead, for good,” Theorem 1.1 and Appendix A. https://zamir.prof/kclq.pdf