¿Hay un nombre para este concepto en Complejidad de comunicación?

8

Deje que Alice y Bob calculen la función booleana .f(x1,,x2n)

Seleccionar un subconjunto aleatorio de cardinalidad y dejar que .n J = { 1 , ... , 2 n } II{1,,2n}nJ={1,,2n}I

Deje que Alice obtener las variables , donde y Bob obtener donde . i I x j j JxiiIxjjJ

Deje que la complejidad de la comunicación de esta función en esta partición seaCCI,J(f)

c c m a x ( f ) = max I

ccmin(f)=minI{1,,2n}J={1,,2n}I|I|=|J|=nCCI,J(f)
ccmax(f)=maxI{1,,2n}J={1,,2n}I|I|=|J|=nCCI,J(f)

¿Existe un término para ccmax(f)ccmin(f) y ccmax(f)ccmin(f) ?

¿Se introducen y estudian los conceptos relacionados en alguna parte?

También estoy interesado en escenarios donde |I|J|bajo condición ||I|J||logn .

T ....
fuente

Respuestas:

7

Lo que llama se conoce como la complejidad de comunicación de partición en el peor de los casos, y lo que llama se conoce como la complejidad de comunicación de partición en el mejor de los casos. Se han estudiado para varias funciones, puede encontrar algunos resultados en el libro de Kushilevitz y Nisan en el capítulo 7. No conozco a nadie que presente la diferencia o la relación como un parámetro para estudiar. c c m i nccmaxccmin

domotorp
fuente
¿Hay una clase de para la cual la razón es cercana a y una clase de para la cual la razón es cercana ? 1 f nf1fn
T ....
Es para cualquier función trivial y es para la identidad ( ), por ejemplo. Θ ( n ) E QΘ(1)Θ(n)EQ
domotorp
¿Qué partición da menos cc para ? EQ
T ....
1
Cuando por cada la misma persona obtiene y , cada persona puede verificar la igualdad de sus índices. x i y iixiyyo
domotorp
Entonces, para la complejidad de la parición, la matriz de comunicación no solo permuta. ¿Podría mutar en algo totalmente diferente?
T ....