  We develop lower bounds on communication in the memory hierarchy or between
processors for nested bilinear algorithms, such as Strassen's algorithm for
matrix multiplication. We build on a previous framework that establishes
communication lower bounds by use of the rank expansion, or the minimum rank of
any fixed size subset of columns of a matrix, for each of the three matrices
encoding a bilinear algorithm. This framework provides lower bounds for a class
of dependency directed acyclic graphs (DAGs) corresponding to the execution of
a given bilinear algorithm, in contrast to other approaches that yield bounds
for specific DAGs. However, our lower bounds only apply to executions that do
not compute the same DAG node multiple times. Two bilinear algorithms can be
nested by taking Kronecker products between their encoding matrices. Our main
result is a lower bound on the rank expansion of a matrix constructed by a
Kronecker product derived from lower bounds on the rank expansion of the
Kronecker product's operands. We apply the rank expansion lower bounds to
obtain novel communication lower bounds for nested Toom-Cook convolution,
Strassen's algorithm, and fast algorithms for contraction of partially
symmetric tensors.
