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

7

EDIT - 2/11/20 - barring mistakes, this should answer the posted question. Summary. Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-deterministic Turing Machine $M$, define its language $L(M)$ to be the set of inputs $x$ to $M$ such that, among all non-deterministic executions of $M$ on input $x$, ...

6

The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-m matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$. (I originally posted this as a comment. I post it as an answer by lack of any other answers.)

3

We can compute the rank of a $m \times n$ matrix A in $\tilde{O}(\textrm{nnz}(A) + r^{\omega})$ time, where $\textrm{nnz}(A)$ is the number of non-zero entries in $A$ and $r$ is the rank of $A$. This follows from Theorem 1.1 in Cheung et. al. [CKL'13] and binary searching over $r$. This is faster than the $O(mn^{\omega-1})$ algorithm mentioned above.

2

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n ... 1 This is NP-hard, by reduction from ILP feasibility. Deciding feasibility of an ILP instance is NP-hard, so your problem is, too. You can convert each inequality$a_1 x_1 + \dots + a_n x_n \ge b$into an equality using a slack variable$s \ge 0$: $$a_1 x_1 + \dots + a_n x_n - s = b.$$ You can arrange for all variables to be non-negative by defining$x_i = ...

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