Complexidade de comunicação para distribuições de produtos

Question

Em geral para o problema (duas partes) Problema de desança para insumos de comprimento n, sabemos que as partes precisam comunicar $ \ ômega (n) $ . Surpreendentemente, hoje descobri (se eu entendi corretamente) que isso não é verdade para distribuições de produtos, isto é, quando os insumos de Alice e Bob são escolhidos independentemente de distribuições arbitrárias! Neste papel , por exemplo, eles fornecem um limite superior com complexidade de comunicação $ \ mathcal {o} (\ sqrt {n} \ log (1 / \ epsilon)) $ , onde $ \ epsilon $ É algum termo de erro não é relevante para a pergunta aqui. Agora estou curioso sobre se as lacunas existem para outros problemas de complexidade de comunicação bem conhecida.

Pergunta: Quais outros problemas bem conhecidos exibem uma lacuna entre as complexidades de comunicação quando se considera distribuições arbitrárias de entrada e distribuições de produtos. Existem resultados semelhantes para produtos internos ou interseções?

Answer 1

Definir a disjunta é mais fácil para distribuições de produtos, uma vez que a distribuição dura para defina disjunta está muito longe de ser uma distribuição de produtos. O que precisamos de uma distribuição dura $ (x, y) $ para o produto interno? Queremos que cada um dos $ x, y $ separadamente para ser bastante aleatório, e queremos $ x \ cdot y $ Para ser principalmente zero, digamos $ x \ cdot y $ contém no máximo uma única $ 1 $ . Isso não pode ser realizado por uma distribuição de produtos. Enquanto você pode obter a $ x \ cdot y $ propriedade, isso implica que cada uma das duas entradas será muito tendenciosa. Por outro lado, se as entradas $ x, y $ são bastante aleatórios, então $ x \ cdot y $ tem muitas $ 1 $ s.

A função do produto interno não sofre com o mesmo problema. De fato, parece que a distribuição mais difícil é a distribuição uniforme. Você pode provar um limite inferior linear usando o método de discrepância - isso é padrão e usa um limite na discrepância conhecida como lema lindsey .

Sherstov veio com um exemplo de lacuna ideal em seu papel Complexidade de comunicação em distribuições de produtos e produtos sem fins lucrativos . Sua função é uma função aleatória, escolhida para que não haja grande monocromático $ 1 $ -rectangles. O resultado final é uma função cuja complexidade de comunicação randomizada é $ \ ômega (n) $ , mas para qualquer distribuição de produtos, a complexidade de comunicação randomizada é $ o (1) $ .