Límites en momentos de frecuencia aproximados

Sea una secuencia de enteros donde cada a j ∈ { 1 , 2 , ... , n } . Para i ∈ { 1 , 2 , ... , n } , sea m i = | { j : a j = i } | . El k ésimo momento de frecuencia se define como$a_1, a_2,\dotsc, a_m$$a_j \in \{1,2,\dotsc,n\}$$i \in \{1,2,\dotsc,n\}$$m_i = |\{j : a_j = i\}|$$k$

$\displaystyle F_k = \sum_{i=1}^n m_i^k.$

En su conocido artículo, La complejidad espacial de aproximar los momentos de frecuencia , Alon et al. proporcione un algoritmo de transmisión que se aproxime a usando aproximadamente O ( n 1 - $F_k$espacio. También utilizan técnicas de complejidad de comunicación para obtener un límite inferior deΩ(n1-$O(n^{1-\frac{1}{k}}(\log n + \log m))$parak>5. Parak=0,1,2, proporcionan más o menos límites superiores e inferiores coincidentes.$\Omega(n^{1-\frac{5}{k}})$$k > 5$$k = 0,1,2$

¿Ha habido mejoras en estos límites desde entonces, y ha habido progreso para ?$k = 3,4,5$

$F_k$$n^{1-2/k}$$k > 2$

Para k <= 2

$O(1/\epsilon^2+log(n))$

$\tilde{O}(log(log(n))$

3) k = 2, creo que el boceto AMS de su trabajo es óptimo

Algo relacionado

$F_\alpha$$\alpha$$\epsilon$$n$