The Discrepancy Method

The Discrepancy Method: Randomness and Complexity

偶然ソフトヒープに関する話題(?)を見つけたので，この本を紹介します．
著者であるChazelleの主な結果の「1つ」に最小費用全域木をO(mα(m,n))時間で求めるアルゴリズムがありますが，その中でソフトヒープが使われています．この本の最後の章に説明があります．
Chazelleの説明は分かりやすいといえるものではないのですが，彼の結果はどれも目を見張るもので，感動ものです．
ちなみにこの本の原稿はChazelleのページからダウンロードもできます．

Chazelleが2006年日本に来たとき講演を聴きましたが，やっぱりテクニカルなところは何をいいたいのかよくわかりませんでした．ボーっと聴く分には全然問題ないんですが，やはり理解したいと思うとかなりハードルが高かったです．