Apakah ada nama untuk konsep ini dalam Kompleksitas Komunikasi?

Biarkan Alice dan Bob menghitung fungsi boolean .$f(x_1,\dots,x_{2n})$

Pilih subset acak dari kardinalitas n dan membiarkan J = { 1 , ... , 2 n } ∖ saya .$\mathcal I\subseteq\{1,\dots,2n\}$$n$$\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$

Mari Alice mendapatkan variabel mana saya ∈ I dan Bob mendapatkan x j di mana j ∈ J .$x_i$$i\in\mathcal I$$x_j$$j\in\mathcal J$

Biarkan kompleksitas komunikasi fungsi ini di bawah partisi ini menjadi $CC_{\mathcal I,\mathcal J}(f)$

$$cc_{min}(f)=\min_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$ $$cc_{max}(f)=\max_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$

Apakah ada istilah untuk dan ?$cc_{max}(f)-cc_{min}(f)$$\frac{cc_{max}(f)}{cc_{min}(f)}$

Apakah konsep terkait diperkenalkan dan dipelajari di mana saja?

Saya juga tertarik pada skenario di manadalam kondisi .$|\mathcal I|\neq\mathcal J|$$||\mathcal I|-\mathcal J||\leq \log n$

Apa yang Anda sebut dikenal sebagai kompleksitas komunikasi partisi terburuk, dan apa yang Anda sebut dikenal sebagai kompleksitas komunikasi partisi terbaik. Ini telah dipelajari untuk beberapa fungsi, Anda dapat menemukan beberapa hasil dalam buku Kushilevitz dan Nisan di bab 7. Saya tidak mengetahui ada orang yang memperkenalkan perbedaan atau rasio sebagai parameter untuk dipelajari.$cc_{max}$$cc_{min}$