18 votes

Why is fast matrix multiplication impractical?

Matrix multiplication based on Strassen's algorithm is in $O(n^{\log(7)/\log(2)})$ and is quite practical. As far as I am aware, for any exponent $\omega<\log(7)/\log(2)$ the corresponding ...
user avatar
  • 8,928
17 votes
Accepted

Faster computation of p-adic log

There is a method with bit complexity $O(n \log^3 n)$, which is an adaptation of the "bit-burst algorithm" for real and complex functions. The idea here is to integrate the solution of a ...
user avatar
12 votes

Why is fast matrix multiplication impractical?

I acknowledge that the question concerns Boolean matrix multiplication. However, a good deal of the opposition to fast matrix multiplication algorithms is due on stability issues that can arise when ...
user avatar
9 votes

Faster computation of p-adic log

Fredrik Johansson gave a very good answer, but I feel like preprint's notation is a bit too dense and abstract (with finite extensions, uniformizers, ramifications and such), so I'll try to recap its ...
user avatar
9 votes

What is the most "informative" Yes/No math question you know?

We could encode several interesting YES/NO questions into one YES/NO question with a suitable function, for example XOR: Is it true that the number of YES answers to the following questions is even? ...
4 votes

Why is fast matrix multiplication impractical?

As an example, Strassen's algorithm can multiply two 2n x 2n matrices by doing 7 multiplications and 18 additions of n x n matrices. So you save one multiplication for 18 additions of n x n matrices. ...
user avatar
3 votes

Why is fast matrix multiplication impractical?

Addressing the Boolean part. Usually, fast matrix multiplication relies heavily on the element type being a ring; in particular, that every element has an additive inverse. For example, Strassen's ...
user avatar
3 votes

Algorithms to factorize words into product of powers

Unfortunately, I couldn't easily find a paper that solves exactly this problem. But I believe the algorithm from Factorizing Strings into Repetitions can be adapted to solve the problem. They find a ...
user avatar
3 votes
Accepted

NP-hardness of non-decision problems

A definition of NP-hard is: if the problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. This definition works for function problems. Example: Consider ...
user avatar
  • 3,861
2 votes

What is the most "informative" Yes/No math question you know?

A general strategy: Since you state that the yes/no answer will come with a proof, I presume the proof will be understandable by humans, so it will need to contain much background material. I would ...
1 vote

Computing moments of discrete probability distribution

Here's a bit more direct way than with Vandermonde transpose. Consider the generating function $$ f(x) = \sum\limits_{k=0}^\infty m_k x^k $$ It rewrites as $$ f(x) = \sum\limits_{k=0}^\infty \sum\...
user avatar
1 vote

Sparse dense matrix versus non-sparse dense matrix in eigenvalue computation

If you take the transpose of the matrix, which has the same eigenvalues, and you divide by $w_0$, you get the (block) companion matrix of a quadratic matrix polynomial with $n \times n$ coefficients. ...
user avatar

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