Avance en la Complejidad Espacial Óptima para la Estimación de Momentos de Frecuencia

Un artículo de Mark Braverman y Or Zamir demuestra un límite inferior de espacio óptimo de Ω(log(nε²)/ε²) para la estimación de momentos de frecuencia, donde ε = Ω(1/√n). Esta investigación resuelve un problema de larga data en la complejidad computacional, coincidiendo con el límite superior clásico de Alon-Matias-Szegedy en un cierto rango. Para valores más pequeños de ε, el artículo también introduce un algoritmo mejorado que refina aún más la complejidad espacial de la estimación de momentos de frecuencia. Este avance proporciona una guía teórica crucial para el procesamiento de datos de flujo y el diseño de algoritmos.