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 ...
16
votes
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 ...
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 ...
13
votes
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 ...
12
votes
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 ...
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 ...
12
votes
Estimating the rank of a large sparse matrix
There is a very neat randomized algorithm by Cheung, Kwok, and Lau, which computes the rank of an $n\times m$ matrix $A$, $n\le m$, in time $O(\mathrm{nnz}(A) + \min\{n^\omega, n\cdot\mathrm{nnz}(A)\})...
11
votes
Status of Raghavendra's algorithm for solving linear systems in finite fields
This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf
10
votes
Accepted
The minimum number of arithmetic operations to compute the determinant
It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant. See for ...
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 ...
9
votes
Non-Orthogonal Vectors Problem
When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).
Recently I ...
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)$. ...
8
votes
Accepted
Status of Raghavendra's algorithm for solving linear systems in finite fields
The paper by Raghavendra is now also published and available here under the title:
Correlation Decay and Tractability of CSPs, appeared in the 43rd International Colloquium on Automata, Languages, ...
8
votes
Accepted
Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?
The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ ...
7
votes
Number of solutions for a system of linear equations over a finite ring
The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\...
7
votes
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 ...
6
votes
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 ...
6
votes
Accepted
Min Hamming distance of a given string from substrings of another string
Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:
Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.
Define polynomials $$p(x,y) = \sum_{i \...
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$ ...
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).
6
votes
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 ...
6
votes
How many multiplications are needed to compute the determinant of a 3×3 matrix?
I have a partial answer to this now.
I still don’t know whether anyone had ever explicitly written down a method for computing the 3×3 determinant using 8 multiplications, but anyone with sufficient ...
6
votes
Accepted
Strongly polynomial time algorithm for shortest convex combination
It is known via a paper of De Loera, Haddock and Rademacher that a strongly polynomial time algorithm for finding a minimum norm point in a simplex implies a strongly polynomial time algorithm for ...
5
votes
Accepted
Estimating the rank of a large sparse matrix
This has also been studied from the property testing / query complexity point of view. For example:
Li, Wang, & Woodruff. Improved Testing of Low Rank Matrices, KDD '14. (Freely available ...
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
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. ...
5
votes
Accepted
Has anyone mixed linear algebra with formal language theory in this way?
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 ...
5
votes
Checking equivalence of two polytopes
The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
linear-algebra × 227ds.algorithms × 62
matrices × 52
cc.complexity-theory × 44
reference-request × 20
graph-theory × 15
linear-programming × 15
matrix-product × 15
optimization × 14
time-complexity × 14
co.combinatorics × 10
approximation-algorithms × 10
quantum-computing × 10
circuit-complexity × 8
randomized-algorithms × 8
coding-theory × 8
computational-geometry × 8
dc.parallel-comp × 8
spectral-graph-theory × 8
na.numerical-analysis × 8
graph-algorithms × 7
np-hardness × 7
sparse-matrix × 7
boolean-matrix × 6
finite-fields × 6