Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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

### Memory requirement for fast matrix multiplication

The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See Space complexity of Coppersmith–Winograd ...
• 26.2k
Accepted

### What are the consequences of solving XOR 3-SAT in Logspace?

Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your ...
• 1,027

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

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

### Checking equivalence of two polytopes

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in ...

### 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,267

• 35.6k

### 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,712
Accepted

### Finding the number of independent rows of a matrix

(what follows solves the question for columns, easily adapted to rows either by transposing or by doing a column echelon instead of a row one) You can do the following: put your matrix in reduced ...
• 676
Accepted

• 9,358

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

### Dichotomy of the spectra of directed graphs

The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as ...
• 14.7k

### Non-Orthogonal Vectors Problem

If $k=O(\log n)$ I believe the techniques of Alman, Chan, and Williams give the best known solution to the Non-Orthogonal Vectors Problem. (They phrase it differently, as a Hamming closest pair ...
• 932

### Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...
• 8,133
How you choose your vector $\nu$ for every terminal symbol you must have a row with exactly one $\epsilon$ in your matrix so that it is a fixed point. So we could disregard terminal symbols, and what ...