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\...
17
Expanding my comment:
Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1.
We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a bipartite graph $G$ with left vertices $[n]$ and right vertices $[n]$, where the edge $(i,j)$ is present if and only if $M_{i,j}=1$. A perfect matching is a subset ...
16
If you allow the repetition of matrices, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A_i =A_j $, then your problem is actually undecidable.
Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).
A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the ...
16
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 ...
15
The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.
It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you ...
15
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.
12
Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that
there exists an efficiently computable matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
the sign rank of $S$ is at least $d$.
So the algorithm computes $M$ and outputs ...
12
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 ...
12
The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.
12
For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)
12
It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at ...
12
Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$
Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
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
Matrices A and B whose elements are in a field F are similar (in F) if and only if they have the same Frobenius normal form. According to a quick search, it seems that the Frobenius normal form of an n×n matrix can be computed with O(n3) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix ...
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
10
The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.
Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.
The type of reductions you'd need ...
9
According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known.
According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z_{\mathrm{sq}}mn)$$
where
$$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure ...
9
This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history).
A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can ...
9
Here's just a couple of observations I couldn't fit in a comment:
0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity.
1) In ...
9
An observation too long for a comment (and which also fits well with Jason Gaitonde's observation-too-long-for-comment):
As hinted at in the OQ, both of these can in fact be realized by a very simple kind of recursive construction. Namely, we specify $B_0 \in \{(0), (\pm 1)\}$ (a $1 \times 1$ matrix), and then a single recursive formula
$$
B_n = \left(\...
8
The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\...
8
You can do this in uniform NC, see:
G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089
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
The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).
There's a nice article that covers this on Wikipedia, based on a simpler proof ...
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$, ...
7
Yes, it is in $\mathsf{NC}^2$:
Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.
The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, ...
7
The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices.
J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal on Matrix Analysis and Applications 28(3):805–821.
The technical report version of the article is available here:
J. K. Reid and J. A. Scott, Reducing ...
7
If you do not allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The interest in computational geometry is that range counting can be encoded as matrix-vector multiplication.) For example, the following lower bounds on the size of ...
7
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.)
6
This is a special case of the following problem: given a polytope $P$ specified by linear constraints and a point $x$ find $y \in P$ that minimizes $\|x - y\|_2^2$.
If you are ok with a small additive approximation to $\|x - y\|_2^2$, you can try using the Frank-Wolfe algorithm. This is a sort of gradient descent algorithm. You start from a point $y_0 \in ...
Only top voted, non community-wiki answers of a minimum length are eligible
