Por que a conjectura de classificação de log usa classificação acima dos reais?

10

Na complexidade da comunicação, a conjectura de log-rank afirma que

cc(M)=(logrk(M))O(1)

Onde é a complexidade da comunicação de e é a classificação de (como uma matriz) sobre os reais.M ( x , y ) r k ( M ) Mcc(M)M(x,y)rk(M)M

No entanto, quando você está apenas usando o método de classificação para diminuir o limite pode usar sobre qualquer campo que seja conveniente. Por que a conjectura de log-rank se restringe a rk sobre os reais? A conjectura é resolvida para sobre campos de característica diferente de zero? Caso contrário, é interessante ou há algo especial sobre over ?r k r k r k Rcc(M)rkrkrkR

Artem Kaznatcheev
fonte
2
BTW Eu acredito que você deve restringir M para ser binário, caso contrário, você pode inventar contra-exemplos triviais.
Sasho Nikolov
@SashoNikolov O que você quer dizer com contra-exemplos triviais, se M não é 0/1 (eu acredito que você quer dizer mais de reais)?
T ....
Por exemplo, o problema "adivinhe o meu número", ou seja, Alice tem um número em e Bob precisa produzi-lo. É fácil ver que a complexidade da comunicação é o log N, mas a classificação da matriz é 1 . {1,,N}logN1
Sasho Nikolov
@SashoNikolov Você pode definir adivinhar meu número com precisão? Não consigo visualizar a matriz característica. Alice tem Bob tem y , então qual é a função f ( x , y ) a partir da qual M da classificação 1 é definida? xyf(x,y)M1
T ....
11
A função é onde x e y são vetores de n bits. Se a definição de complexidade da comunicação exigir que o valor de f seja determinado inteiramente pela transcrição do protocolo (esta é a definição em Kushilevitz-Nisan), então claramente a complexidade é n . f(x,y)=xxynfn
Sasho Nikolov

Respostas:

14

A conjectura falha em . Olhada M ( x , y ) = x , y mod 2 , e x , y { 0 , 1 } n . A complexidade da comunicação é Ω ( n ) , mas a classificação de M sobre F 2 é n , pela linearidade do produto interno.F2M(x,y)=x,ymod2x,y{0,1}nΩ(n)MF2n

Sasho Nikolov
fonte