{"id":"arxiv:2006.14652","kind":"preprint","title":"Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication","authors":["Ojas Parekh","Cynthia A. Phillips","Conrad D. James","James B. Aimone"],"author_count":4,"year":2020,"published":"2020-06-25","venue":null,"cited_by":null,"doi":"10.1145/3210377.3210410","arxiv_id":"2006.14652","nct_id":null,"source_url":"https://arxiv.org/abs/2006.14652","archive_url":"https://space-kitty.com/papers/arxiv:2006.14652","updated":"2020-06-25","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2006.14652","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","cs.DC","cs.NE"],"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":[]}