From a realized nine-vertex recursion to faster word-RAM clique counting
ProvedVWZClique.NativeTraversal.wordRam_of_realizesclique-countingfine-grained-complexityword-ram
Suppose the weighted nine-vertex clique recursion has a fixed logarithmic-word RAM program for each sufficiently large clique size . On every sufficiently large input graph, the program must return the recursion's exact value and spend at most its recursive cost times a fixed power of the bit length. If the square multiplication cost satisfies for every , where is the saving for nine-vertex patterns with at most 36 edges, then some works for all sufficiently large : the number of -cliques can be computed on the word RAM in time.
Preamble
import Mathlib import Definitions.Def_VWZClique_NativeCliqueCompiler
Formal statement
theorem VWZClique.NativeTraversal.wordRam_of_realizes {mm : ℕ → ℕ} {M : ℝ} (hM : 0 < M)
(hmm : ∀ n : ℕ, 1 ≤ n → (mm n : ℝ) ≤ M * (n : ℝ) ^
(OAI.MatrixMultiplication.Arithmetic.omega ℂ +
(VWZClique.UniformFolds.levelSaving 36).val / 8))
{T U A : ℕ} (native : VWZClique.NativeTraversal.Realizes mm T U A) :
∃ δ : ℝ, 0 < δ ∧ ∃ K₀ : ℕ, ∀ k ≥ K₀,
VWZClique.countsWithin k
((OAI.MatrixMultiplication.Arithmetic.omega ℂ - δ) * (k : ℝ) / 3) := 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