Counting large cliques with arithmetic circuits
ProvedVWZClique.count_large_cliques_arithmeticarithmetic-circuitsfine-grained-complexityk-cliquematrix-multiplication
There are absolute constants and such that the following holds for every characteristic-zero field and every fixed . On the adjacency entries of an undirected simple graph with labeled vertices, one arithmetic circuit counts its unordered -cliques using at most
arithmetic operations. The circuit can depend on . Every graph at that size uses the same circuit. The cost includes construction of the grouped weights from the adjacency entries.
Preamble
import Definitions.Def_VWZClique_Count import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega open OAI.MatrixMultiplication.Arithmetic VWZClique Classical
Formal statement
theorem VWZClique.count_large_cliques_arithmetic :
∃ δ : ℝ, 0 < δ ∧ ∃ K : ℕ, ∀ (F : Type*) [Field F] [CharZero F], ∀ k ≥ K,
∃ D : ℝ, 0 < D ∧ ∀ n : ℕ, 1 ≤ n →
∃ (r : ℕ) (p : Program F (Fin n × Fin n) r) (o : Fin r),
(p.cost : ℝ) ≤ D * (n : ℝ)^((omega F - δ) * (k : ℝ) / 3) ∧
∀ G : SimpleGraph (Fin n),
p.eval (fun ij => if G.Adj ij.1 ij.2 then 1 else 0) o = (count G k : F) := by sorrySource
Virginia Vassilevska Williams and Or Zamir, The k-Clique hypothesis is dead, for good, https://zamir.prof/kclq.pdf, Section 3, proof of Theorem 1.1 (p. 14). Arithmetic-circuit corollary with sorted, padded vertex blocks.