線形時間アルゴリズムの壁を破る：亜線形時間アルゴリズムの台頭

線形時間アルゴリズムは長年、問題解決のゴールドスタンダードとされてきました。しかし、巨大なデータセットの普及に伴い、亜線形時間アルゴリズムがますます注目を集めています。亜線形時間アルゴリズムは入力データのごく一部しか読み込まないため、一見不可能に思えます。決定的な亜線形時間アルゴリズムが一部の問題に存在する一方で、ほとんどの問題ではランダム化が必要となり、近似解が得られます。近年、古典的な最適化問題やプロパティテストなど、さまざまな問題でブレークスルーが達成されています。Szemerédiの正則性補題や低ランク行列近似などの手法が、亜線形アルゴリズムの設計に役立っていますが、その範囲と限界についてはまだ多くのことが解明されていません。