Timeline for Why is the probability of a false positive not 0 for Freivald's Algorithm?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 14, 2021 at 11:10 | comment | added | Emil Jeřábek | ... complexity of integer multiplication. Thus, if I want error $2^{-t}$, I need time $O\bigl(tn^2\frac{M(m+r)}r\bigr)$; since $M$ grows superlinearly, this is minimized for $r\approx m$, in which case the time is $O\bigl(tn^2\frac{M(m)}m\bigr)$, for $t\ge m$. This is $O(tn^2m)$ using schoolbook quadratic multiplication, and $O(tn^2\log m)$ using (theoretically) best known multiplication algorithms. | |
| Jul 14, 2021 at 11:04 | comment | added | Emil Jeřábek | Well, what I’d rather do is that when checking multiplication of $n\times n$ integer or rational matrices with entries of bitsize $m$, pick the vector $v$ in $\{0,\dots,2^m-1\}^n$. The point is that this will not significantly increase the complexity because you’ve already paid the price: you have to do arithmetic operations on numbers of size $\Omega(m)$ anyway. More formally, if $n$ and $m$ is as above, and I run the algorithm $k$ times independently with uniform $v\in\{0,\dots,2^r-1\}^n$, the probability of error is $2^{-kr}$, and the running time is $O(kn^2M(m+r))$ where $M$ is the ... | |
| Jul 14, 2021 at 9:26 | comment | added | Alex B. | If you're careful, you may not increase the complexity by changing the sample space. You could for example choose your vector so that all entries are in $\{0,1\}$ except for one entry which is in $\{0,\dots, 2^{n}-1\}$. That one entry appears in at most $O(n)$ sums and products, and it increases the complexity of the sum/product by at most $O(n)$, so you only get an additional $O(n^2)$ factor, which is fine. There may still be some hope that the sample space that Frievalds used could be improved upon to yield a better bound. | |
| Jul 14, 2021 at 7:55 | comment | added | Emil Jeřábek | @MarioCarneiro You can sure tinker with the probability in various ways. For example, choosing $v$ in $\{0,\dots,2^n-1\}^n$ will decrease the probability to $2^{-n}$. However, no matter what you do, the probability is not $0$ (it is inversely proportional to the size of the sample set for each coordinate), and there is a trade off in that choosing $v$ from a larger sample set will increase the size of the numbers involved in the computation, hence increase the complexity of the algorithm. | |
| Jul 14, 2021 at 4:10 | comment | added | D.W.♦ | @MarioCarneiro, nope, that doesn't help. Consider $$AB-C = \begin{pmatrix}0&0&0\\0&0&0\\1&-1&0\end{pmatrix}$$. | |
| Jul 14, 2021 at 2:23 | comment | added | Mario Carneiro | Wouldn't you do a lot better by choosing $v$ from $\{1,2\}^n$ instead? It seems obvious that you don't want the zero vector in the distribution since that's a guaranteed false positive, and zero entries in the vector more generally cause problems when the difference matrix has lots of zero entries like in your example. | |
| Jul 13, 2021 at 22:58 | vote | accept | Alex B. | ||
| Jul 13, 2021 at 22:55 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 701 characters in body
|
| Jul 13, 2021 at 22:52 | comment | added | D.W.♦ | @KeimaKatsuragi, see edited answer. | |
| Jul 13, 2021 at 19:04 | comment | added | Alex B. | This is a good answer, and I appreciate it. However, in practice, I mainly multiply matrices over $\mathbb{Q}$. In that case, the same proof follows. In particular, when I perturb a LP for the simplex method to create nondegeneracy, I do exactly that and the justification also follows from hyperplanes being measure zero. Is there a reason why we should not do so in the rational case? Thanks again. | |
| Jul 13, 2021 at 5:52 | history | answered | D.W.♦ | CC BY-SA 4.0 |