https://twitter.com/kinaba のログ (twilog の方が便利です。)
| http://arxiv.org/abs/1404.0799 (from FOCS14) 読んでた。3SUM問題（n個の実数から3つ選んで足して0にできるか判定）は単純なO(n^2)解より速く解けんという予想があったが解けちゃったという話。色んな問題の下限予想が3SUMに帰着されてたので影響ある | |
| 続) 前半の、比較演算の個数だけで数えるならば O(n^1.5 √(log n)) 回で良い(意訳)という定理が面白かった。このジャンルだと基本技っぽいのだけど、a+b<c+d ⇔ a-c<d-b という当たり前of当たり前な式変形が強力すぎて驚愕する。鳩の巣原理の神応用ぽさある | |
| あとそういえば入門書も読みました https://t.co/IU2uCQbKCf 大変ダムだった | |
| @ir5 decision tree と RAM で o(n^2) になっているという話だと思います。チューリングマシンでは、はい |