Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Josh Alman's user avatar
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 ...
Ryan Williams's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Gustav Nordh's user avatar
  • 1,047
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)\})...
Sasho Nikolov's user avatar
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
user43170's user avatar
  • 163
11 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 ...
A. Rex's user avatar
  • 276
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 ...
smapers's user avatar
  • 849
10 votes
Accepted

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

For notational convenience define r.v.s $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$. ...
Neal Young's user avatar
  • 10.8k
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 ...
Lijie Chen's user avatar
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, ...
LeoW.'s user avatar
  • 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$ ...
Emil Jeřábek's user avatar
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 $\...
Joshua Grochow's user avatar
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 ...
Rasmus Pagh's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Robin Houston's user avatar
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 ...
Chandra Chekuri's user avatar
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 ...
Joshua Grochow's user avatar
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)$.
walkerbacker's user avatar
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. ...
Neal Young's user avatar
  • 10.8k
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 ...
StefanH's user avatar
  • 2,077
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 ...
Jacques Carette's user avatar
5 votes

What are some good resources for strengthening my theoretical foundation for machine learning?

I suggest Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal. Probability is at the foundation of machine learning and it's one of the weakest ...
Aryeh's user avatar
  • 10.6k
5 votes
Accepted

What is the complexity of this submatrix selection problem?

EDIT: Added an answer meeting the unique-sum requirement. Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique. Proof. Here's the reduction. First ...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

Reference request for linear algebra over GF(2)

Strangely, linear algebra specific to finite fields is best studied in textbooks on the theory of error-correcting codes (for example, MacWilliams and Sloane). Pretty much all familiar notions in ...
Mahdi Cheraghchi's user avatar
4 votes

Bigger picture behind the choice of matrices in the Strassen algorithm

Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are: Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the ...
Joshua Grochow's user avatar
4 votes

Memory requirement for fast matrix multiplication

More generally, fast matrix multiplication can be done on $p$ processors in $O(n^2/p)$ memory per processor. However, the communication between processors is then suboptimal. Optimal communication can ...
Alexander Tiskin's user avatar
4 votes

Complexity of reachability in linear dynamical systems over finite fields

For clarity, I'm going to generalize your question to be over characteristic $p > 0$ (with base field $\mathbb{F}_q$) instead of the specific case of $p=q=2$. I'll take $p$ and $q$ as a fixed ...
Andrew Morgan's user avatar
4 votes
Accepted

Rank-robustness of the parallel complexity of linear algebra problems

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$. If you have a matrix of size $n \times 2 \log n$, you can ...
Markus Bläser's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible