오랜 난제 풀렸다: randomized query complexity가 certificate complexity를 앞서다
Randomized query complexity can beat certificate complexity
query complexity 분야의 오랜 미해결 문제는 R(f) << C(f)를 만족하는 total Boolean function이 존재하는지였다. Shalev Ben-David와 Robin Kothari는 R(f) = O~(sqrt{C(f)})인 함수를 구성해 이를 해결했으며, 이는 log factor를 제외하면 최적이다. 같은 함수는 Q(f) = O~(C(f)^{1/4})도 만족해 quantum query complexity에서도 거의 최적의 결과를 낸다.
A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) <<C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors.