2026/03/31 by Chengu Wang
Computer Science · #cs.CC #cs.DS #msc:68Q17 #msc:15A69 #msc:68W30 #msc:12Y05 #acm:68Q17 #acm:15A69 #acm:68W30 #acm:12Y05
arxiv created 2026/07/30 · arxiv updated 2026/07/31
We present a general, automated framework for proving lower bounds on the bilinear complexity (tensor rank) of multiplication problems over a finite field \mathbbFq. The framework is parameterized only by the multiplication tensor and by a group of rank-preserving symmetries acting on one argument: it classifies the orbits of constraint subspaces under that group, runs a dynamic program over the orbits combining four lower-bound techniques, and emits a proof certificate that a verifier rechecks, typically faster than the search. Instantiating the framework for matrix multiplication, we improve the lower bounds for four small formats over \mathbbF2, most notably showing that the bilinear complexity of multiplying two 3 × 3 matrices over \mathbbF2 is at least 20, raising the bound of 19 that had stood since Bläser (2003). Instantiating it for polynomial multiplication -- full products, cyclic convolution, and the truncated (modulo xN) and negacyclic (modulo xN+1) products -- we obtain eighteen new lower bounds over \mathbbF2 and \mathbbF3. Every bound is backed by a machine-checkable certificate.