長年の未解決問題が決着、randomized query complexityはcertificate complexityを上回れる

Randomized query complexity can beat certificate complexity

query complexityにおける長年の未解決問題は、R(f) << C(f)となるtotal Boolean function fが存在するかどうかだった。Ben-DavidとKothariはR(f) = O~(sqrt{C(f)})となる関数を構成し、これはlog因子を除いて最適である。同じ関数はQ(f) = O~(C(f)^{1/4})も満たし、こちらもほぼ最適だ。論文はわずか6ページ。