30
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
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 ...
- 401
17
votes
Accepted
Matrix permanent is 0
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 ...
- 2,783
14
votes
Accepted
Complexity of k-clique for hypergraphs
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 ...
- 26.6k
13
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
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 ...
- 35.9k
12
votes
Finding the sparsest solution to a system of linear equations
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 ...
- 2,295
12
votes
Approximating the sign rank of a matrix
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 ...
- 18k
12
votes
Complexity of matrix powering
For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)
- 2,279
10
votes
Accepted
The complexity of the permanent of low rank matrices
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 ...
- 814
9
votes
Accepted
Exact formula for the number of spanning trees of a rectangle
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$ ...
- 50.3k
9
votes
Accepted
Matrix vector multiplication algorithm using minimal number of additions
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 ...
- 35.9k
9
votes
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
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\}^...
- 740
9
votes
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
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 ...
- 35.9k
8
votes
Accepted
Matrix multiplication with transpose
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)$. ...
- 565
7
votes
Accepted
Can we decide whether a permanent has a unique term?
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-...
- 8,346
7
votes
Matrix vector multiplication algorithm using minimal number of additions
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 ...
- 18k
6
votes
Matrix permanent is 0
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.
- 942
6
votes
Finding the sparsest solution to a system of linear equations
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$ ...
- 5,732
6
votes
Accepted
Graph isomorphism problem with invertible adjacency matrices
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).
- 1,897
6
votes
similar matrices
There are indeed other restrictions on $P$ that relate this problem to GI. For example, if one requires that $P$ be a Kronecker (tensor) product $P_1 \otimes P_2 \otimes P_3$, then the resulting ...
- 35.9k
6
votes
Low rank Log rank conjecture
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
- 746
6
votes
Accepted
What's the complexity of factoring over a set of generators (say in $GL_2$)?
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 ...
- 35.9k
6
votes
Accepted
Complexity of $\{0,\pm1\}$ determinant in sparse cases?
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 ...
- 35.9k
5
votes
Accepted
Arithmetic complexity of matrix powering
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 ...
- 35.9k
5
votes
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
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)$.
- 136
5
votes
Rate of convergence for the Perron–Frobenius theorem
See the power method for computing eigenvectors:
http://en.wikipedia.org/wiki/Power_iteration
Convergence is exponential (geometric in the ratio of the top two eigenvalues).
- 10.1k
5
votes
Accepted
Canonisation of boolean matrices under row and column permutations
This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, ...
- 35.9k
5
votes
Algebraic account of Gaussian elimination?
You really should read Gowers' essay carefully - it cleanly details the reasons why you need a basis in general. So if there is going to be an algebraic account of Gauss-Jordan, it will necessarily ...
- 1,500
4
votes
Finding the sparsest solution to a system of linear equations
This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers.
In signal processing, the matrix and the vectors have ...
- 2,271
4
votes
Finding the sparsest solution to a system of linear equations
This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.
- 9,378
Only top scored, non community-wiki answers of a minimum length are eligible