Complexidade da comunicação para decidir a associatividade

12

Let { 0 , . . . , N - 1 } e : S × S S . Eu quero calcular a complexidade da comunicação para decidir se é associativo.S=0,...,n1:S×SS

O modelo é o seguinte. é dada como uma matriz M . Alice (resp. Bob) recebe metade das entradas da matriz aleatoriamente (o mesmo para Bob). Quero calcular o número do pior caso de entradas que Alice deve enviar para Bob para que Bob possa decidir sobre a associatividade de .M

Na verdade, é simples para reduzir o problema de decidir a igualdade de dois cordões de tamanho bit para o problema de decidir a associatividade de sobre S . Isso significa que a complexidade da comunicação da associatividade é mais baixa delimitada por Ω ( n ) . No entanto, suspeito que esse LB não seja rígido. Sendo definido em uma entrada do tamanho n 2 , eu preferiria encontrar uma complexidade de comunicação de Ω ( n 2 ) .Ω(n)SΩ(n)n2Ω(n2)

Existe um resultado conhecido sobre esse problema? A resposta é por um motivo óbvio que não estou vendo?n2

Sylvain Peyronnet
fonte
Você poderia explicar o modelo com mais detalhes? Como que contribuições Alice e Bob recebem, e se isso é aleatório ou determinístico (ou quântico)?
Robin Kothari
Eu editei de acordo. Estou interessado em coisas aleatórias ou determinísticas (mas não quânticas), mesmo que praticamente apenas o arcabouço determinístico seja importante para mim (pretendo usar o resultado para provar LB no tamanho de um OBDD).
Sylvain Peyronnet
1
Eu acho que isso geralmente é chamado compl de comunicação unidirecional, pois Bob não tem permissão para enviar nenhum bit para Alice no seu modelo.
Domotorp # 3/10

Respostas:

10

nn2Snf(t)

Per Vognsen
fonte
1
Obrigado, examinarei este documento e volto aqui para informá-lo.
Sylvain Peyronnet