# Tag Info

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

13

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

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

4

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?

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

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

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

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.

2

I found an answer in the paper "Fast sparse matrix multiplication" as Theorem 2.4. The authors cite "Fast rectangular matrix multiplications and applications", so that's the original source, I guess. It is possible to do it in a black-box fashion, so it works for any fast multiplication algorithms. That, of course, does not prove ...

2

Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta_1,\ldots,\beta_{n^2})^T$, and the $n+1$'th column is $(\alpha_1,\ldots,\alpha_{n^2})^T$. If $\beta_i=\alpha_i-1$ for all $1\leq i\leq n^2$, then the $n+1$'th column is a linear combination of the first and ...

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