# Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication

Preprint · Ojas Parekh, Cynthia A. Phillips, Conrad D. James, James B. Aimone

- Archive id: arxiv:2006.14652
- Published: 2020-06-25
- DOI: https://doi.org/10.1145/3210377.3210410
- arXiv: https://arxiv.org/abs/2006.14652
- Source URL: https://arxiv.org/abs/2006.14652
- PDF: https://arxiv.org/pdf/2006.14652
- Provenance: arxiv

## Abstract

Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two $N$ by $N$ matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform $O(N^ω)$ arithmetic operations for a positive constant $ω\< 3$. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately $O(N^ω)$ gates. Prior to our work, it was not known whether the $Θ(N^3)$-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option.

_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.