Percée dans la complexité spatiale optimale pour l'estimation des moments de fréquence
2024-12-29
Un article de Mark Braverman et Or Zamir démontre une borne inférieure optimale de l'espace de Ω(log(nε²)/ε²) pour l'estimation des moments de fréquence, où ε = Ω(1/√n). Cette recherche résout un problème de longue date en complexité computationnelle, concordant avec la borne supérieure classique d'Alon-Matias-Szegedy dans une certaine plage. Pour des valeurs plus petites de ε, l'article introduit également un algorithme amélioré qui affine encore la complexité spatiale de l'estimation des moments de fréquence. Cette percée fournit des indications théoriques cruciales pour le traitement des données de flux et la conception d'algorithmes.