Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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
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
  • 849
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
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
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
  • 10.8k
7 votes
Accepted

Approaches to fast matrix multiplication and their limits

Their phrase in that paper "All work on matrix multiplication since 1986" is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of ...
Joshua Grochow's user avatar
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

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
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
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
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

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
4 votes

Bigger picture behind the choice of matrices in the Strassen algorithm

Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are: Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the ...
Joshua Grochow's user avatar
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,514
3 votes

Positive topological ordering, take 3

This paper, Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette, shows that the problem is NP-complete for binary square matrices.
Mohammad Al-Turkistany's user avatar
3 votes

What is the fastest algorithm to compute rank of a rectangular matrix?

We can compute the rank of a $m \times n$ matrix A in $\tilde{O}(\textrm{nnz}(A) + r^{\omega})$ time, where $\textrm{nnz}(A)$ is the number of non-zero entries in $A$ and $r$ is the rank of $A$. This ...
Ainesh Bakshi's user avatar
3 votes
Accepted

Properties of convex polytope of 0-1 matrices

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
Andrew Morgan's user avatar
3 votes
Accepted

What is computational complexity of calculating the Variance-Covariance Matrix?

Your conjecture is correct. If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from ...
dopexxx's user avatar
  • 148
3 votes
Accepted

Time complexity for multiplying two lower triangular matrices

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can ...
Pranav Bisht's user avatar
3 votes

Ordering of sub problems in dynamic programming

This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance $I$ then the recursion generates several subproblems. You can obtain a ...
Chandra Chekuri's user avatar
3 votes
Accepted

Problem conditions to use Laplacian solvers

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition ...
smapers's user avatar
  • 849
3 votes
Accepted

Finding output with unique witness in matrix multiplication

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one ...
Ryan Williams's user avatar
3 votes

Johnson-Lindenstrauss and the largest eigenvalue of a matrix

I had thought I used something like this in a previous paper, but on checking I only needed the vector-based version. I'm not quite sure how to get the upper bound, but I think you can get the lower ...
Christopher T. Chubb's user avatar
3 votes

Johnson-Lindenstrauss and the largest eigenvalue of a matrix

The answer to this question is no - thanks to Pravesh Kothari for the solution below and appreciate ideas from Clement Canonne and Christopher Chubb. Consider two cases: 1) A is rank one, in which ...
anurag anshu's user avatar
3 votes

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

Theorem 3.2 in this paper: https://doi.org/10.1007/s00224-003-1077-7 says this: Let B be an n × n matrix, whose entries are each polynomials of degree n in Z[x], where the coefficients of each ...
Eric Allender's user avatar
2 votes

Open/unsolved problems in (computational) random matrix theory / matrix completion?

Not sure if this is the kind of thing you want but here is something I find fascinating : This particular breakthrough paper's proof technique is in a sense "random matrix theory", https://arxiv.org/...
Student's user avatar
  • 654
2 votes

Decomposing outer product or general rank factorization over $\Bbb F_q$

There might be faster algorithms, but it is easy to compute such a factorization (for any $r$) from the reduced row-echelon form of $M$: set $M_2$ to be the RREF with zero rows removed, and $M_1$ to ...
Andrew Morgan's user avatar
2 votes

Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

We can make one observation: adaptive access to the oracle doesn't help. You might as well fix in advance the set of queries you plan to make to the oracle. So, the condition is that there has to ...
D.W.'s user avatar
  • 12.1k

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