# Tag Info

### 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 ...
• 421

### 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 ...
• 37.8k
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 ...
• 849

### 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 ...
• 37.8k

• 1,429
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 ...
• 148

### 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 ...
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 ...
• 27.5k

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

### 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 ...
• 253

### 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 ...
• 2,271

### Complexity of Finding the Eigendecomposition of a Matrix

Here is a relatively recent answer that answers this (mostly) in the affirmative: Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time Where the ...
• 121

### 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 ...
• 1,429

### 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 ...
• 12.3k
Accepted

### Complexity involving connected components of 0/1 matrix

So I give a sketch why the problem is NP-complete. It is very sketchy, which you can take as a sign of trust that you're a smart guy, and not at all a sign of laziness on my part. We will reduce a ...
• 14.1k
You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$. The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i....