STOC 2010のY. Dodis, M. Pătraşcu, M. Thorupのが面白そうだとは思わんかね。 A[1...n] in {0,...,9}^nなるベクトルを考える。10進n桁の整数である。計算機上（PRAMでモデル化してる）で、各桁 A[i]を読み書きする機能を高速化しつつ保存容量をなるべく小さ…