# Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication

Preprint · Benjamin Rossman

- Archive id: arxiv:2406.16015
- Published: 2024-06-23
- arXiv: https://arxiv.org/abs/2406.16015
- Source URL: https://arxiv.org/abs/2406.16015
- PDF: https://arxiv.org/pdf/2406.16015
- Provenance: arxiv

## Abstract

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete problem of computing the product of $k$ $n$-by-$n$ Boolean matrices with at most a single $1$ in each row and column. For all $d \\le \\log k$, this problem is solvable by $n^{O(dk^{1/d})}$ size monotone formulas of two distinct types: (unbounded fan-in) $AC^0$ formulas of depth $d+1$ and (semi-unbounded fan-in) $SAC^0$ formulas of $\\bigwedge$-depth $d$ and $\\bigwedge$-fan-in $k^{1/d}$. The results of this paper give matching $n^{Ω(dk^{1/d})}$ lower bounds for monotone $AC^0$ and $SAC^0$ formulas for all $k \\le \\log\\log n$, as well as slightly weaker $n^{Ω(dk^{1/2d})}$ lower bounds for non-monotone $AC^0$ and $SAC^0$ formulas. These size-depth tradeoffs converge at $d = \\log k$ to tight $n^{Ω(\\log k)}$ lower bounds for both unbounded-depth monotone formulas \[Ros15\] and bounded-depth non-monotone formulas \[Ros18\]. Our non-monotone lower bounds extend to the more restricted Iterated Permutation Matrix Multiplication problem, improving the previous $n^{k^{1/\\exp(O(d))}}$ tradeoff for this problem \[BIP98\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.