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

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

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

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

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

Community wiki

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

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

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

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

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

Community wiki

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

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

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

#### Related Tags

computational-complexity × 1190algorithms × 211

co.combinatorics × 208

graph-theory × 184

nt.number-theory × 133

computer-science × 112

lo.logic × 109

computability-theory × 94

reference-request × 86

np × 71

computational-number-theory × 53

linear-algebra × 49

gr.group-theory × 42

combinatorial-optimization × 33

polynomials × 31

ag.algebraic-geometry × 30

oc.optimization-and-control × 30

matrices × 27

pr.probability × 26

prime-numbers × 24

graph-colorings × 23

approximation-algorithms × 22

discrete-geometry × 21

cryptography × 20

integer-programming × 19