32 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 ...
Josh Alman's user avatar
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 ...
Thomas's user avatar
  • 2,803
15 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 ...
Joshua Grochow's user avatar
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 ...
Ryan Williams's user avatar
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 ...
Joe Bebel's user avatar
  • 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 ...
Sasho Nikolov's user avatar
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 ...
smapers's user avatar
  • 839
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 ...
Joshua Grochow's user avatar
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$ ...
David Eppstein's user avatar
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\}^...
Jason Gaitonde's user avatar
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 ...
Joshua Grochow's user avatar
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)$. ...
Vladimir Lysikov's user avatar
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-...
Neal Young's user avatar
  • 9,595
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 ...
Sasho Nikolov's user avatar
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.
Rasmus Pagh's user avatar
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$ ...
Gamow's user avatar
  • 5,762
6 votes

Low rank Log rank conjecture

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
Shachar Lovett's user avatar
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).
Igor Shinkar's user avatar
  • 1,897
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 ...
Joshua Grochow's user avatar
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 ...
Joshua Grochow's user avatar
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)$.
walkerbacker's user avatar
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 ...
Joshua Grochow's user avatar
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, ...
Joshua Grochow's user avatar
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 ...
Jacques Carette's user avatar
4 votes
Accepted

Checking properties of matrices

The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even ...
Marc's user avatar
  • 686
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.
R B's user avatar
  • 9,428
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 ...
argentpepper's user avatar
  • 2,281
4 votes
Accepted

Low-depth arithmetic complexity of the product of $k$ matrices

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of ...
Bruno's user avatar
  • 4,439

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