30

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\...


18

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7 The reduction is from Vertex Cover and is very nice. Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+...


15

De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix ...


13

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result. François le Gall recently improved on Coppersmith's work, and his paper has just been ...


12

Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of Coppersmith-Winograd) - would "simply" produce a family of algorithms $A_\epsilon$ running in time $O(n^{2+\epsilon})$. So to have a single algorithm which ran in $O(n^2 ...


11

Josh Alman showed some cool lower bound results of MM, which won CCC 2019 best student paper award! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf


11

There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases $A_0,A_1,A_2,A_3$ and $B_0,B_1,B_2,B_3$ of the space of $2\times 2$ real matrices which satisfy the following property: $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$. Furthermore, $A_0 = B_0$. To ...


10

The fastest way to multiply dense matrices on a modern computer is to call BLAS.


9

As others have said, there's no point in reinventing the wheel. If you must implement it yourself for whatever reason, then you should either go for the naïve or Strassen algorithm. Naïve is faster for smaller matrices, but as matrix size increases to ~100 you will find that the Strassen algorithm starts to perform better as the impact of the larger ...


8

No. Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$


7

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit ...


7

Like many other questions, the answer to this one can be found in Stothers' thesis. A local USP is a CWP in which the only way in which a 1-piece, a 2-piece and a 3-piece can fit together is if their union is in $S$. Clearly a local USP is a USP, and a construction from [CKSU] shows that the USP capacity is achieved by local USPs (we are going to show that ...


6

I'll first answer question (2). Let's solve the $(\max,+)$ product problem. The $(\min,+)$ product can be solved analogously by negating entries and adding $M$ to each entry to make all entries positive. Take $A$ and $B$ whose product $C$ we want to compute, and create matrices $A'$ and $B'$ where $A'[i,j]=(n+1)^{A[i,j]}$ and $B'[i,j]=(n+1)^{B[i,j]}$ for ...


5

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations http://dx.doi.org/10.1016/j.jco.2005.04.002 Prior to this, Kaltofen and Villard gave improved algorithms, see http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1


5

Commutative algorithms are not studied that much, because you cannot use them recursively by cutting larger matrices into smaller blocks like you do in Strassen's algorithm. Since every noncommutative algorithm is a commutative one, commutative algorithms can be trivially as efficient as noncommutative ones.


5

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated ...


5

Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$. UPDATE: I missed the main diagonal part of the question. Even computing the main diagonal is as hard as matrix multiplication: denote $f(A, B) = \operatorname{tr}(A^TBA) = \sum_{i,j,k} a_{ij} b_{ik} a_{kj}$. The derivatives $...


4

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of exhaustivity): Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix ...


3

This problem is essentially equivalent to matrix multiplication. Let's look at $\sum_{i=1}^{n}X_{i}RY_{i}$ first, where $X_i$ and $Y_i$ are diagonal matrices. If $A$ is the matrix with the diagonal entries of $X_i$ as the $i$-th column, and $B$ is the matrix with the diagonal entires of $Y_i$ as the $i$-th row, then the entry-wise product of $AB$ and $R$ is ...


3

Consider circuit value problem and Boolean formula evaluation for various small complexity classes. Deterministic sequential time complexity of them are the similar as far as we know, yet they are very different from circuit complexity perspective. Similarity in one particular type of resource on one model doesn't imply similarity for other resources in ...


2

I'd say that the gap in the arithmetic settings tells us that matrix multiplication is inherently a much more parallel task than the determinant. In other words, while the sequential complexities of both problems are closely related, their parallel complexities are not that close from each other. A relevant paper is Fast parallel matrix inversion algorithms ...


2

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.


1

Because $\mathbf{c}' = R'\mathbf{p}$ and $R'$ contains 3 nonzero elements in each row.


1

While this doesn't answer your exact question, CFG parsing is a decision problem that was reduced from matrix multiplication (so it is as hard as matrix multiplication in a sense). Specifically, in [1] it was shown that CFG parsing is as hard as boolean matrix multiplication. In particular, if CFG parsing (a decision problem) can be solved in $O(gn^{3-\...


1

This isn't a characterization of NP: it's just an NP-complete problem (well, I assume it's NP-complete, anyway). OK, if so, you could characterize NP as the class of problems reducible to your matrix problem but how are you going to define reductions? Using reductions from some existing model of computation (e.g., Turing machines) would be self-defeating. ...


1

This probably doesn't belong on the TCS stack exchange, but I'll answer anyways. No, multiplication by a permutation matrix will never change the rank of the matrix. Permutation matrices are orthogonal, so if matrix M has an SVD: $$ M = U \Sigma V^* $$ Then the product $MP$ has an SVD: $$ MP = U \Sigma V^* P = U \Sigma W^* $$ Recall that the rank is the ...


Only top voted, non community-wiki answers of a minimum length are eligible