Complexidade de comunicação com um árbitro

Assuma uma estrutura na complexidade da comunicação em que temos dois jogadores A (piolhos) e B (ob) e um R (eferee). A e B não se comunicam diretamente entre si. Em cada rodada de comunicação, cada um deles envia uma mensagem ( , m B ) para o R. R calcula duas funções f A ( m A , m B ) e f B ( m $m_A$$m_B$$f_A(m_A,m_B)$ e envia os resultados para eles. As funções são fixas. A ideia é que a comunicação entre os jogadores seja restrita. Além disso, o árbitro pode fazer algum processamento nas mensagens.$f_B(m_A,m_B)$

Exemplo:

A e B enviam dois números (grandes arbitrariamente) para R, R verifica qual deles é maior e informa os jogadores.

Nesta estrutura, podemos projetar um protocolo simples que calcula facilmente a função a seguir usando uma única rodada. A e B enviam $x$ e para R, R retorna a resposta para eles e eles a resposta.$y$

Obviamente, este não é um caso interessante, uma vez que a função que estamos computando é a mesma das funções de árbitro. Um caso mais interessante é quando temos uma desigualdade linear fixo e os valores para as variáveis são repartida entre jogadores (A tem → x e B tem → y ). A tarefa é decidir se a desigualdade está correta. O protocolo neste caso é que os jogadores calculem sua parte e os enviem ao árbitro.$\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$$\vec{x}$$\vec{y}$

Questão:

Este tipo de complexidade de comunicação foi estudado? Se sim, onde posso encontrar mais informações sobre isso?

nota 1: na página 49 Kushilevitz e Nisan mencionam uma estrutura que envolve um árbitro, mas parece muito diferente do que estou perguntando.

nota 2: Não tenho certeza se chamar R como árbitro é a coisa certa. Comente se você tem uma sugestão melhor.

Tenho certeza que você conhece o artigo a seguir, mas coloquei um link para ele, porque outros leitores podem estar interessados: Interpolação por jogos

Este artigo é uma tentativa de usar a estrutura de complexidade da comunicação para mostrar limites inferiores para planos de corte. O protocolo é usado para produzir um circuito interpolante para CNF insatisfatório:

O jogador recebe as entradas a e y a , o jogador B recebe b e z b . Se houver uma prova superficial em forma de árvore nos planos de corte, os dois jogadores terão um protocolo de comunicação tal que$A$$a$$y^a$$B$$b$$z^b$

• qualquer comunicação é mediada pelo árbitro, o que ajuda a avaliar as desigualdades na prova;
• a quantidade de comunicação é pequena (a árvore é rasa);
• os dois jogadores decidem qual de ou B é falsificado;$A$$B$
• eles encontram uma posição em que um i ≠ b i .$i$$a_i \not= b_i$

O árbitro é transformado em um protocolo probabilístico de desigualdades. Dessa maneira, é possível converter o limite inferior para protocolos probabilísticos semelhantes a árvores na estrutura de complexidade da comunicação em limite inferior para provas de planos de corte semelhantes a árvores.

Se tivéssemos um limite inferior para o protocolo de comunicação na forma de um PLS, obteríamos um limite inferior para provas de planos de corte semelhantes a dag.

Observe que esta técnica não depende das regras de inferência reais dos planos de corte. Se assumirmos que as regras de inferência são (1) combinação positiva (2) divisão inteira com floor, podemos construir o circuito interpolante monótono usando o argumento Pavel Pudlák .

Apenas algumas observações. Primeiro, não consigo entender por que precisamos de um árbitro. Se sua função é conhecida pelos jogadores, por que eles não podem apenas simular o árbitro? Alice envia para Bob, ele (sem ver m A ) calcula m B , depois calcula f ( m A , m B ) e informa o resultado a Alice. Talvez você assuma que f A não é conhecido por Bob ef f B por Alice? $m_A$$m_A$$m_B$$f(m_A,m_B)$$f_A$$f_B$

Segundo, protocolos relacionados a desigualdades lineares são realmente interessantes no contexto de corte de provas de plano. Nesse caso, é suficiente considerar protocolos, nos quais a forma das mensagens é muito restrita : apenas valores de algumas combinações lineares de variáveis ​​de entrada podem ser comunicados.

Para ser um pouco mais preciso, suponha que recebamos um sistema de desigualdades lineares com coeficientes inteiros. Sabemos que o sistema não tem solução - 1 . As variáveis ​​são de alguma forma divididas entre os jogadores (da maneira cinquenta e cinquenta); este é o cenário da "pior partição": o adversário pode escolher a partição "pior". Dada a 0 - 1 corda, o objetivo dos jogadores é encontrar uma desigualdade insatisfeito. Ou seja, a resposta agora não é nem um pouco, mas o nome de uma desigualdade do nosso sistema. (Este é um jogo de comunicação do tipo Karchmer-Wigderson.)$0$$1$$0$$1$

Agora considere os seguintes protocolos restritos para esse jogo: (i) os árbitros funcionam se apenas se for α ≤ β , (ii) as mensagens dos jogadores são restritas a lineares : em cada rodada, Alice deve enviar a mensagem no formato m A ( → x ) = → c ⋅ → x e Bob a mensagem no formato m B ( → y ) = → d ⋅ → y .$f(\alpha,\beta)=1$$\alpha \leq \beta$$m_A(\vec{x})=\vec{c}\cdot \vec{x}$$m_B(\vec{y})=\vec{d}\cdot \vec{y}$

Impagliazzo, Pitassi e Urquhart (1994) observaram o seguinte: Se todos os coeficientes usados ​​nas provas do plano de corte são polinomiais no número de variáveis ​​e se esse jogo precisa de bits de comunicação, todas as provas semelhantes à árvore da insatisfação do sistema dado deve produzir desigualdades exp ( t / log n ) . Eles então usaram limites inferiores conhecidos na complexidade da comunicação para fornecer um sistema explícito que requer provas de tamanho exponencial. A desvantagem desse resultado é que o sistema é muito artificial , não corresponde a nenhum problema de otimização "real". Portanto, é uma questão interessante apresentar um limite inferior para problemas de otimização "reais". $t$$\exp(t/\log n)$

$G=(V,E)$$u$$x_u$$\sum_{v\in V}x_v>\alpha(G)$$x_u+x_v\leq 1$$uv$$G$$0$$1$solução para o subsistema dessas últimas desigualdades fornece um conjunto independente em , todo o sistema não possui soluções zero-one. Qual é a complexidade da comunicação dos jogos para esses sistemas?$G$

Se nosso gráfico é bipartido, é natural (para o adversário) dividir as variáveis ​​de acordo com suas partes. Nesse caso, Alice obtém um subconjunto A ⊆ L , Bob um subconjunto B ⊆ R com a promessa de que | A ∪ B | > a ( G ) . O objetivo é encontrar uma aresta entre A e B . Aqui α ( G $=(L\cup R,E)$$A\subseteq L$$B\subseteq R$$|A\cup B|>\alpha(G)$$A$$B$$\alpha(G)$é o "bipartite" número de independência: o tamanho máximo de um conjunto independente não inteiramente situada em ou R . Um dos meus problemas favoritos é: Prove que existem n × n gráficos que requerem ω ( log 2 n ) bits de comunicação . $L$$R$$n\times n$$\omega(\log^2 n)$

@ Kaveh: Desculpe por "responder" à sua pergunta com perguntas.