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 ...
- 421
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 ...
- 27.3k
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 ...
- 36.9k
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 ...
- 1,047
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 ...
- 371
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 ...
- 2,295
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)\})...
- 18.1k
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
- 163
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 ...
- 266
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 ...
- 839
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 ...
- 176
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)$. ...
- 632
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, ...
- 118
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$ ...
- 16.8k
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 $\...
- 36.9k
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 ...
- 962
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 ...
- 686
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 \...
- 2,803
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$ ...
- 5,772
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).
- 1,897
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 ...
- 16.8k
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 ...
- 761
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 ...
- 6,979
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 ...
- 36.9k
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)$.
- 136
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. ...
- 9,595
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 ...
- 2,037
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 ...
- 377
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 ...
- 1,530
Only top scored, non community-wiki answers of a minimum length are eligible