Límites en momentos de frecuencia aproximados

11

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 comoa1,a2,,amaj{1,2,,n}i{1,2,,n}mi=|{j:aj=i}|k

Fk=i=1nmik.

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 - 1Fkespacio. También utilizan técnicas de complejidad de comunicación para obtener un límite inferior deΩ(n1-5O(n11k(logn+logm))parak>5. Parak=0,1,2, proporcionan más o menos límites superiores e inferiores coincidentes.Ω(n15k)k>5k=0,1,2

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

Timothy Sun
fuente

Respuestas:

14

Fkn12/kk>2

Suresh Venkat
fuente
3
Esto también es relevante: arxiv.org/abs/1011.1263
Mahdi Cheraghchi
1
Verifique el enlace que envió @MCH, hace que el algoritmo y el análisis sean simples y malos. Pero tal vez la tesis de David también sea útil para la intuición y la discusión: almaden.ibm.com/cs/people/dpwoodru/phdFinal.pdf
Sasho Nikolov
3

Para k <= 2

O(1/ϵ2+log(n))

O~(log(log(n))

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

Ashwinkumar BV
fuente
1

Algo relacionado

Fααϵn

Ashwinkumar BV
fuente
1
α(1,2)nϵ