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 ...
13
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 ...
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 ...
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
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
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 ...
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
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, ...
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$
8
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.)
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
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
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
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 ...
6
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
6
Yes, your problem is essentially equivalent to the one (General Position) in the Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran paper.
Consider an $n \times m$ matrix $A$, $n < m$. Without loss of generality, assume that $\text{rank}(A) = n$ and the first $n$ columns of $A$ are independent: $A =[B\ |\ D]$, where $B$ is a nonsingular $...
6
Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).
6
If it suffices to know the parity of the permanent, you can compute it in polynomial time by computing the determinant of the matrix over the field of size 2.
6
The problem is NP-complete, by reduction from the following problem:
Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ with $Ax=b$?
For every coordinate $x_i$ of vector $x$,
introduce $100(n+m)$ new equations $x_i+y_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and
introduce $100(...
6
This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$.
Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (...
6
Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.
If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the ...
5
I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.
Only top voted, non community-wiki answers of a minimum length are eligible