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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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\}^...
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 ...
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)$. ...
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 ...
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.
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 ...
6 votes

Low rank Log rank conjecture

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
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 ...
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 ...
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 ...
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)$.
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, ...
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 ...
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