Riffle Rank

Motivated by an application in Algebraic Circuit Complexity, we introduce a complexity measure on even-order tensors called rife rank. The riffle rank of a tensor f: [n]2k → F, denoted Rriffle(f), is the minimum m ≥ 0 such that f admits a sum-product decomposition of the form f(a1,b1,...ak,bk) = σℓ=1mAℓ,1(a1)·Aℓ,2(b1,a2)·...·Aℓ,k(b1,...,bk-1,ak)·Bℓ(b1,...,bk) where Aℓ,i: [n]i → F and Bℓ: [n]k → F. Riffle rank is at most nk for all f and at least (1/2 - o(1))nk for almost all f. We advance a conjecture that the k-fold identity tensor, In⊗k(a1,b1,...,ak,bk) = {1 if (a1,...,ak) = (b1,...,bk), 0 otherwise, has (nearly if not exactly) the maximum possible riffle rank nk. As a rationale for studying this conjecture, we show that an nk-o(log k) lower bound on Rriffle(In⊗k) would imply an nω(logk) lower bound on the arithmetic formula size of the Iterated Matrix Multiplication polynomial IMMn,k and thus separate complexity classes VNC1 and VBP.

Duke Scholars

Author Benjamin Rossman Computer Science