{"id":"arxiv:1612.04208","kind":"preprint","title":"An $O(n^2\\log^4 n \\log \\log n)$ Time Matrix Multiplication Algorithm","authors":["Yijie Han"],"author_count":1,"year":2016,"published":"2016-12-10","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1612.04208","nct_id":null,"source_url":"https://arxiv.org/abs/1612.04208","archive_url":"https://space-kitty.com/papers/arxiv:1612.04208","updated":"2023-07-10","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1612.04208","abstract":"We show, for the input vectors $(a_0, a_1, ..., a_{n-1})$ and $(b_0, b_1, ..., b_{n-1})$, where $a_i$'s and $b_j$'s are real numbers, after $O(n\\log^4 n)$ time preprocessing for each of them, the vector multiplication $(a_0, a_1, ..., a_{n-1})(b_0, b_1, ..., b_{n-1})^T $ can be computed in $O(\\log^4 n \\log \\log n)$ time. This enables the matrix multiplication for two $n\\times n$ matrices to be computed in $O(n^2 \\log^4 n\\log \\log n)$ time.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"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":[]}