Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Small-depth Multilinear Formula Lower Bounds for Iterated Matrix
  Multiplication, with Applications   In this paper, we study the algebraic formula complexity of multiplying $d$
many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show that the
well-known divide-and-conquer algorithm cannot be significantly improved at any
depth, as long as the formulas are multilinear.
  Formally, for each depth $\Delta \leq \log d$, we show that any product-depth
$\Delta$ multilinear formula for $\mathrm{IMM}_d$ must have size
$\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any
multilinear circuit of product-depth $\Delta$ for the same polynomial of the
above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any
polynomial-sized multilinear formula for $\mathrm{IMM}_d$ must have depth
$\Omega(\log d)$, and any polynomial-sized multilinear circuit for
$\mathrm{IMM}_d$ must have depth $\Omega(\log d/\log \log d).$ Both these
bounds are tight up to constant factors.
  1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any
formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth
$O(\log s)$; further, this reduction continues to hold for multilinear
formulas. Our lower bound implies that any depth-reduction in the multilinear
setting cannot reduce the depth to $o(\log s)$ without a superpolynomial
blow-up in size.
  2. Separations from general formulas: Our result, along with a non-trivial
upper bound for $\mathrm{IMM}_{d}$ implied by a result of Gupta, Kamath, Kayal
and Saptharishi (SICOMP 2016), shows that for any size $s$ and product-depth
$\Delta = o(\log s),$ general formulas of size $s$ and product-depth $\Delta$
cannot be converted to multilinear formulas of size $s^{\omega(1)}$ and
product-depth $\Delta,$ when the underlying field has characteristic zero.

32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
34
The categories of this paper are: chem-ph
6
The categories of this paper are: astro-ph
15
The categories of this paper are: nucl-ex
29
The categories of this paper are: funct-an
2
The categories of this paper are: math
27
The categories of this paper are: comp-gas
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn
5
The categories of this paper are: gr-qc
33
The categories of this paper are: plasm-ph
13
The categories of this paper are: quant-ph
24
The categories of this paper are: dg-ga
25
The categories of this paper are: patt-sol
18
The categories of this paper are: econ