{"id":"arxiv:2406.16015","kind":"preprint","title":"Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication","authors":["Benjamin Rossman"],"author_count":1,"year":2024,"published":"2024-06-23","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2406.16015","nct_id":null,"source_url":"https://arxiv.org/abs/2406.16015","archive_url":"https://space-kitty.com/papers/arxiv:2406.16015","updated":"2024-06-23","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2406.16015","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.CC","math.CO"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}