Existe um nome para esse conceito em Complexidade da comunicação?

8

Deixe Alice e Bob calcular a função booleana .f(x1,,x2n)

Seleccionar um subconjunto aleatório de cardinalidade e deixar .I{1,,2n}nJ={1,,2n}I

Vamos Alice obter variáveis onde e Bob obter onde .xiiIxjjJ

Seja a complexidade da comunicação desta função nesta partição serCCI,J(f)

Defina cc_ {max} (f) = \ max _ {\ substack {\ mathcal I \ subseteq \ {1, \ dots, 2n \} \\\ mathcal J = \ {1, \ dots, 2n \} \ barra invertida \ mathcal I \\ | \ mathcal I | = | \ mathcal J | = n}} CC_ { \ mathcal I, \ mathcal J} (f)

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 um termo para ccmax(f)ccmin(f) e ccmax(f)ccmin(f) ?

Os conceitos relacionados são introduzidos e estudados em algum lugar?

Também estou interessado em cenários em que |I|J|sob a condição ||I|J||logn .

T ....
fonte

Respostas:

7

O que você chama de é conhecido como a complexidade de comunicação da partição de pior caso, e o que você chama é conhecido como a complexidade de comunicação da partição de melhor caso. Estes foram estudados para várias funções; você pode encontrar alguns resultados no livro de Kushilevitz e Nisan no capítulo 7. Não conheço ninguém que introduza a diferença ou a proporção como parâmetro para estudar.ccmaxccmin

domotorp
fonte
Existe uma classe de para a qual a razão está próxima de e uma classe de para a qual a razão está próxima de ? f1fn
T ....
É para qualquer função trivial e para a identidade ( ), por exemplo. Θ(1)Θ(n)EQ
Domotorp
qual partição dá o mínimo de cc para ? EQ
T ....
1
Quando para cada a mesma pessoa obtém e , cada pessoa pode verificar a igualdade de seus índices. ixiyi
Domotorp 19/12/16
Portanto, para a complexidade da parição, a matriz de comunicação não apenas permite. Poderia se transformar em algo totalmente diferente?
T ....