From a projected contraction on the word RAM to faster clique counting
ProvedVWZClique.IntegerRAM.NativeArena.wordRam_of_projected_kernelclique-countingfine-grained-complexityword-ram
Let be the arithmetic exponent of complex matrix multiplication, and let be the exponent saving for the formalized recursion on nine-vertex patterns with at most edges. Suppose that the projected contraction has a fixed word-RAM implementation with polynomial workspace, that it returns the exact trace and preserves the suspended recursion frames, and that its runtime satisfies the per-frame bound in ProjectionKernel. If its square multiplication cost obeys for every , then there are constants and such that for each , the number of -cliques in an -vertex graph can be computed on the logarithmic-word RAM in time.
Preamble
import Mathlib import Definitions.Def_VWZClique_NativeProjectionContract open OAI.MatrixMultiplication.Arithmetic VWZClique VWZClique.UniformFolds VWZClique.IntegerRAM.NativeArena
Formal statement
theorem VWZClique.IntegerRAM.NativeArena.wordRam_of_projected_kernel
{mm : ℕ → ℕ} {T : ℕ} (pk : VWZClique.IntegerRAM.NativeArena.ProjectionKernel mm T)
{C : ℝ} (hC : 0 < C)
(rate : ∀ n : ℕ, 1 ≤ n → (mm n : ℝ) ≤ C * (n : ℝ) ^
(OAI.MatrixMultiplication.Arithmetic.omega ℂ + (VWZClique.UniformFolds.levelSaving 36).val / 8)) :
∃ δ : ℝ, 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 (word-RAM implementation). https://zamir.prof/kclq.pdf