30
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 ...
- 401
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 ...
- 26.2k
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,027
13
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 ...
- 35.6k
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
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
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
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)\})...
- 18k
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
9
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 ...
- 256
9
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 ...
- 814
8
votes
Accepted
Parallel (NC) replacements for Gaussian elimination?
Yes, it is in $\mathsf{NC}^2$:
Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.
The following (earlier) ...
- 35.6k
8
votes
Vertices of a polytope
No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-...
- 50.2k
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)$. ...
- 565
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$ ...
- 14.7k
8
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 ...
- 121
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 $\...
- 35.6k
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,712
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 ...
- 676
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,743
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,887
6
votes
Accepted
Is there a polynomial time algorithm for creating a set of vectors in general position?
Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x_1, \ldots, x_n)$, $y = (y_1, \ldots, y_m)$ be sequences of pairwise distinct numbers. The corresponding Cauchy ...
- 18k
6
votes
Accepted
Finding the minimum number of coordinates to change to get a vector inside a subspace
This problem is NP-hard in general.
This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that
$$Ay = -Ax$$
As finding a sparsest solution vector for an underdetermined system ...
- 9,358
6
votes
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
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 ...
- 14.7k
6
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 ...
- 932
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. ...
- 8,133
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 ...
- 1,947
Only top scored, non community-wiki answers of a minimum length are eligible