Combinatorial Boolean Matrix Multiplication in n3/2Ω((log⁡n))n^{3}/2^{\Omega }(\sqrt{(\log n)}) Time

Piaoyang Cui, Yiming Liu, David P. Woodruff

Cui, Liu and Woodruff give deterministic combinatorial algorithms that multiply two n×nn\times n Boolean matrices or decide if an nn-vertex graph contains a triangle in O(n3/2Ω(log⁡n))O(n^3/2^{\Omega(\sqrt{\log n})}) time.

What was already known

Abboud, Fischer, Kelley, Lovett and Meka obtained O(n3/2Ω((log⁡n)1/7))O(n^3/2^{\Omega((\log n)^{1/7})}) time using a graph decomposition and asked whether the exponent 1/21/2 could be reached.

AI involvement AI-led

The authors set the problem and direction. They credit Gemini 4 agents with developing the algorithms and proofs and writing the Lean formalization. The authors verified and edited the paper.

Importance Notable

The result reaches the proposed square-root exponent in the saving over cubic time for both problems.

Technical verification Formal (Lean + human)

Cui, Liu and Woodruff report checking the manuscript. Lean checks formal versions of the decomposition and the two runtime bounds with the documented sampler hypotheses and cost accounting.

Independent checking

The authors report verifying the paper’s proofs and algorithms.

Checker
Piaoyang Cui, Yiming Liu and David P. Woodruff
Scope
Cui, Liu and Woodruff give deterministic combinatorial algorithms that multiply two n×nn\times n Boolean matrices or decide if an nn-vertex graph contains a triangle in O(n3/2Ω(log⁡n))O(n^3/2^{\Omega(\sqrt{\log n})}) time.
Basis
Reported by the linked checker

Formal checking

Checked the core theorem statements under explicit sampler and extractor hypotheses. The cost monad represents operation counts.

Checker
Lean 4 kernel, as reported by the authors
Scope
Cui, Liu and Woodruff give deterministic combinatorial algorithms that multiply two n×nn\times n Boolean matrices or decide if an nn-vertex graph contains a triangle in O(n3/2Ω(log⁡n))O(n^3/2^{\Omega(\sqrt{\log n})}) time.
Basis
Reported by the linked checker

Human understanding Few

The authors directed and checked the work. The paper credits the agents with the decomposition and gives no separately attributed human explanation of that step.

Other useful sources

Correction and publication history