La complejidad de consulta aleatorizada puede superar a la complejidad de certificado
Randomized query complexity can beat certificate complexity
Una pregunta abierta durante décadas en teoría de la complejidad: ¿existe una función booleana total f con R(f) << C(f)? Ben-David y Kothari construyen una función con R(f) = O~(sqrt{C(f)}), óptima salvo factores logarítmicos, que además logra Q(f) = O~(C(f)^{1/4}), también casi óptima. El resultado responde afirmativamente a la cuestión.
Una pregunta abierta desde hace mucho tiempo en la complejidad de consultas pregunta si existe una función booleana total f con R(f) << C(f), donde R(f) y C(f) denotan su complejidad de consulta aleatorizada con error acotado y su complejidad de certificado, respectivamente.