From b6b26c90ba01bb12f69dd591056cf2b203b541ff Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Tue, 18 Nov 2014 15:19:33 +0100
Subject: [PATCH] Floyd: Zmineny pokroky v nasobeni matic

---
 14-floyd/14-floyd.tex | 21 +++++++++++++++------
 ga.bib                | 16 ++++++++++++++++
 2 files changed, 31 insertions(+), 6 deletions(-)

diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex
index 9d6ef19..8538921 100644
--- a/14-floyd/14-floyd.tex
+++ b/14-floyd/14-floyd.tex
@@ -186,12 +186,21 @@ odpov
 
 Øe¹íme-li grafové problémy pomocí matic, nabízí se pou¾ít známé subkubické algoritmy
 pro lineárnì algebraické úlohy. Ty jsou obvykle zalo¾eny na efektivním násobení
-matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase $\O(n^{2.808})$ Strassenovým
-algoritmem~\cite{strassen:matmult}, pøípadnì asymptoticky nejrychlej¹ím známým algoritmem od Coppersmithe
-a Winograda~\cite{coppersmith:matmult} v~èase $\O(n^{2.376})$. Slavná hypotéza øíká,
-¾e pro ka¾dé $\omega>2$ existuje algoritmus násobící matice se slo¾itostí $\O(n^\omega)$
-(blí¾e o~tomto fascinujícím tématu viz \cite{szegedy:matmult}). Oznaème tedy~$\omega$
-nejni¾¹í exponent, kterého jsme schopni dosáhnout.
+matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase:
+
+\itemize\ibull
+\:$\O(n^3)$ podle definice,
+\:$\O(n^{2.808})$ Strassenovým algoritmem~\cite{strassen:matmult},
+\:$\O(n^{2.376})$ algoritmem Coppersmithe a Winograda~\cite{coppersmith:matmult},
+\:$\O(n^{2.373})$ algoritmem Williamsové~\cite{williams:matmult}.
+\endlist
+
+Obecnì pøijímaná hypotéza øíká, ¾e pro ka¾dé $\omega>2$ existuje algoritmus
+násobící matice se slo¾itostí $\O(n^\omega)$. Jediný známý dolní odhad je pøitom
+$\Omega(n^2\log n)$ pro aritmetické obvody s~omezenou velikostí konstant~\cite{raz:mmlower}.
+Blí¾e se o~tomto fascinujícím tématu mù¾ete doèíst v~Szegedyho èlánku \cite{szegedy:matmult}.
+
+Pøedpokládejme tedy, ¾e umíme násobit matice v~èase $\O(n^\omega)$ pro nìjaké $\omega < 3$.
 
 Co se stane, kdy¾ mocníme matici sousednosti~$A$ grafu? V~matici $A^k$ se na pozici
 $i,j$ nachází poèet sledù délky~$k$, které vedou z~vrcholu~$i$ do vrcholu~$j$.
diff --git a/ga.bib b/ga.bib
index 8a6fc48..4c2bb29 100644
--- a/ga.bib
+++ b/ga.bib
@@ -748,3 +748,19 @@
   pages={325--357},
   year={2004},
 }
+
+@inproceedings{ williams:matmult,
+  title={{Multiplying matrices faster than Coppersmith-Winograd}},
+  author={{Williams, V. V.}},
+  booktitle={STOC '12: Proceedings of the 44th annual ACM Symposium on Theory of Computing},
+  pages={887--898},
+  year = {2012},
+}
+
+@inproceedings{ raz:mmlower,
+  title={{On the complexity of matrix product}},
+  author={{Raz, R.}},
+  booktitle={STOC '02: Proceedings of the 34th annual ACM Symposium on Theory of Computing},
+  pages={144-151},
+  year = {2002},
+}
-- 
2.39.5