Publications [#386051] of Benjamin Rossman

Papers Published

1. Rossman, B, Riffle Rank, Procedia Computer Science, vol. 273 (January, 2025), pp. 215-222 [doi]
   (last updated on 2026/01/15)

   Abstract:
   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.