Investigadores han demostrado que una variante normalizada de la jerarquía de Kikuchi logra el equilibrio teórico conjeturado entre la fuerza de la señal y el tiempo de resolución para el problema kXOR. Este avance elimina las pérdidas logarítmicas que afectaban a análisis espectrales previos, las cuales se traducían en un aumento exponencial en el tiempo de ejecución. El estudio valida la conjetura de que el nivel $\ell$ de la jerarquía de Kikuchi puede resolver problemas con $m \gtrsim \rho^{-2}n^{k/2}/\ell^{k/2-1}$ cláusulas en un tiempo $n^{O(\ell)}$, donde $\rho$ es el sesgo de la señal plantada o la ventaja objetivo para la refutación.

Los algoritmos desarrollados en esta investigación permiten una detección robusta, una recuperación débil y una refutación fuerte en la escala mencionada. Un paso adicional de limpieza mejora la recuperación débil a una recuperación exacta, y los certificados de refutación generan pruebas de suma de cuadrados de grado $O_k(\ell)$. Además, el estudio establece límites inferiores coincidentes en el mismo modelo, lo que confirma la optimalidad de los resultados. Las cotas superiores de inferencia y refutación son aplicables a leyes de plantación y predicados más generales.

Las pruebas se basan en dos elementos clave: una normalización de la matriz de Kikuchi dispersa y un recuento preciso de los caminos cerrados en su expansión de traza. Este enfoque también se ha utilizado en un trabajo complementario para demostrar la conjetura del límite de Moore para hipergrafos de Feige (2008). Adicionalmente, los autores presentan un algoritmo cuántico que ofrece una aceleración cuártica sobre los algoritmos espectrales clásicos para las tareas de detección y recuperación débil.