Qual é a maior lacuna entre a classificação e a classificação aproximada?

10

Sabemos que o log da classificação de uma matriz 0-1 é o limite inferior da complexidade da comunicação determinística, e o log da classificação aproximada é o limite inferior da complexidade da comunicação aleatória. A maior lacuna entre a complexidade determinística da comunicação e a complexidade aleatória da comunicação é exponencial. Então, e quanto à diferença entre classificação e classificação aproximada de uma matriz booleana?

pyao
fonte
11
qual é a "classificação aproximada" de uma matriz?
Suresh Venkat
7
A classificação aproximada ϵ de uma matriz booleana M é a classificação mínima de uma matriz real A que difere de M por no máximo ϵ em qualquer entrada (cf. Buhrman e Wolf 2001, "Complexidade da comunicação em limites inferiores por polinômios"). Seria útil editar a pergunta para explicar isso (se for a definição desejada) e descrever o papel de ϵ (já que a diferença de classificação depende claramente de ϵ ).
Mjqxxxx

Respostas:

9

Primeiro, darei algumas informações e definirei a classificação aproximada. Uma boa referência é a recente pesquisa de Lee e Schraibman Lower Bounds on Communication Complexity .

Definição: Seja uma matriz de sinais. A classificação aproximada de com fator de aproximação , denotada , éAAαrankα(A)

rankα(A)=minB:1A[i,j]B[i,j]αrank(B) .

Quando , definaα

rankα(A)=minB:1A[i,j]B[i,j]rank(B) .

Um resultado de Krause diz que que e são complexidade da comunicação em moeda privada com erro com limite de com erro com limite superior por .Rϵpri(A)logrankα(A)α=1/(12ϵ)RϵpriAϵ

O acima foi para o fundo. Agora, para responder à pergunta, Camas e Simon mostrou que caracteriza completamente a complexidade de comunicação de erros ilimitada de . Eles também demonstraram que esta concorda com a dimensão mínima de um arranjo compreendendo a função booleana cuja matriz de comunicação é . A complexidade da comunicação de erro ilimitado da função de igualdade é . Tenha isso em mente.rank(A)AAO(1)

A matriz de comunicação para igualdade é apenas a identidade, ou seja, uma matriz booleana com linhas e colunas com todas na diagonal. Vamos denotar isso por . Alon mostrou que o que é muito próximo de um fator logarítmico (com o teorema de Krause, obtemos ).2n2nI2nrank2(I2n)=Ω(n)Rϵpri(EQ)=Ω(logn)

A matriz de identidade possui classificação completa, ou seja, . Portanto, temos separações exponencialmente grandes para e .2nα=2α

Marcos Villagra
fonte
Obrigado. mas minha pergunta é se existe um intervalo superexponencial para a e a , onde mas não . rank(A)rankα(A)α>1α
pyao
aah eu vejo, mas isso não está escrito na pergunta. Que eu saiba, a maior diferença é exponencial.
Marcos Villagra
11
Marcos fornece uma referência que mostra uma diferença de entre e . como pode haver uma lacuna superexponencial quando o tamanho da matriz é ? 2n/nrankrank22n
Sasho Nikolov
você quer dizer uma lacuna de vez de ? Ω(2n)2Ω(n)
Sasho Nikolov 28/11
Sasho faz um bom argumento, o que você quer dizer com "superexponencial? Para qualquer problema de comunicação, a matriz está sempre acabada .{0,1}n×{0,1}n
Marcos Villagra