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 ∈ Jxii∈Ixjj∈J
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 ⊆
c cm i n( f) = minyo⊆ { 1 , ... , 2 n }J= { 1 , ... , 2 n } ∖ IEl | yoEl | = | JEl | =nCCyo, J( f)
c cm a x( f) = maxyo⊆ { 1 , ... , 2 n }J= { 1, ... , 2 n } ∖ IEl | yoEl | = | JEl | =nCCyo, J( f)
¿Existe un término para c cm a x( f) - c cmetroi n( f) y Ccmetroa x( f)Ccm in( f) ?
¿Se introducen y estudian los conceptos relacionados en alguna parte?
También estoy interesado en escenarios donde El |yoEl | ≠ JEl |bajo condición El | El | yoEl | - JEl | El | ≤lognorte .