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

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

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

• 35.9k
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,378
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 ...
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

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.9k
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
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,783

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,722
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.9k

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 ...
• 942

Rate of convergence for the Perron–Frobenius theorem

See the power method for computing eigenvectors: http://en.wikipedia.org/wiki/Power_iteration Convergence is exponential (geometric in the ratio of the top two eigenvalues).
• 10.1k
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)$.