Matriz balanceada explícita

20

É possível construir uma explícita 0 / 1 -matrix com N 1,5 queridos tal que cada N 0,499 × N 0,499 submatrix contém menos de N 0,501 queridos?N×N 0/1N1.5N0.499×N0.499N0.501

Ou provavelmente é possível criar um conjunto de batidas explícito para essa propriedade.

É fácil ver que a matriz aleatória tem essa propriedade com probabilidade exponencialmente próxima a . Além disso, o lema de mistura do expansor não é suficiente para derivar essa propriedade.1

Eu acho que geradores pseudo-aleatórios que enganam retângulos combinatórios podem ajudar aqui, mas eles são projetados para distribuições uniformes e eu basicamente preciso de aqui.B(N2,N0.5)

ilyaraz
fonte
5
É uma pergunta interessante: embora eu esteja curioso sobre a motivação.
Suresh Venkat
@Suresh É proveniente da não extração quantitativa de informações mútuas. Se você estiver interessado, eu posso elaborar.
Ilyaraz
Na verdade eu sou. você pode me enviar um e-mail ([email protected]) se for mais fácil assim.
Suresh Venkat

Respostas:

11

O que você procura é um extrator de um bit para duas fontes independentes: uma função , de modo que, desde que X, Y sejam variáveis ​​aleatórias com entropia mínima 0,499 * log (N), E (X, Y) está quase equilibrado.E:[N]×[N]{0,1}

É um problema difícil notório. Para os parâmetros que você deseja, acredito que foi resolvido pela Bourgain. Veja aqui: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Dana Moshkovitz
fonte
1
Bourgain fornece um viés para alguns α > 0 . Eu não tenho certeza que a análise pode dar α = 1 / 2 . Se eu fosse você, estudaria e verificaria. Você também pode perguntar a Anup Rao, Zeev Dvir, Avi Wigderson ou qualquer outra pessoa que trabalhou nesse problema. p=Nαα>0α=1/2
Dana Moshkovitz
7
@ilyaraz: Quando você (ou alguém) descobrir se a construção da Bourgain fornece ou não a matriz desejada, compartilhe (a menos que você se importe)!
Tsuyoshi Ito
1
essa foi uma pergunta e resposta muito interessante. Vou responder ao pedido de Tsuyoshi.
Suresh Venkat
2
Relendo a pergunta e a resposta (já faz um tempo ...), acho que não percebi que o questionador queria apenas N ^ {1.5}, o que corresponde a extrair um pouco 1 com probabilidade N ^ {-0,5} em vez de um pouco equilibrado. Ainda assim, acho que a referência aos extratores de duas fontes é útil. Eu posso imaginar que técnicas semelhantes seriam úteis para o cenário da pergunta.
Dana Moshkovitz
1
1) Se um extrator produzir k bits quase uniformes, em particular, você poderá obter um bit 1 com probabilidade ~ 1/2 ^ k. 2) Isso é um grande desperdício, e me parece uma boa pergunta de pesquisa encontrar uma maneira mais eficiente de gerar esses bits.
Dana Moshkovitz
2

Essa resposta é baseada na idéia de Dana na resposta acima.

δ=0.001N=2nf(x,y)(X,Y)nk=n(1/2δ)n=n/2ϵk=n(1/23δ)2k>k+log(1/ϵ)+O(1)

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Condutores de aleatoriedade e expansão em grau constante além do grau / 2 barreiras

ϵ=2knz(x,y)f(x,y)=z21.5nzzO(2n/2)N×N(x,y)1(x,y)f(x,y)=zz21.5n uns.

2k×2kX,Yff(X,Y)ϵk12k+ϵ2k+122kk+1=O(2n/2+δ)

f

MCH
fonte