Jawna zrównoważona macierz

Czy możliwe jest zbudowanie wyraźnej macierzy z , tak aby każda podmacierz zawiera mniej niż ?$N \times N$ $0/1$$N^{1.5}$$N^{0.499} \times N^{0.499}$$N^{0.501}$

Lub prawdopodobnie możliwe jest zbudowanie jawnego zestawu uderzeń dla takiej właściwości.

Łatwo zauważyć, że macierz losowa ma tę właściwość z prawdopodobieństwem wykładniczo bliskim . Również lemat mieszania ekspandera nie jest wystarczający do uzyskania tej właściwości.$1$

Wydaje mi się, że generatory pseudolosowe, które mogą oszukać tutaj kombinatoryczne prostokąty, są jednak zaprojektowane dla jednolitych rozkładów i zasadniczo potrzebuję tutaj .$B(N^2, N^{-0.5})$

To, czego szukasz, to ekstraktor jednobitowy dla dwóch niezależnych źródeł: funkcja , tak że pod warunkiem, że X, Y są zmiennymi losowymi z min-entropią 0,499 * log (N), E (X, Y) jest prawie zrównoważony.E:[N]×[N]→{0,1}$E:[N]\times [N]\to \{0,1\}$$E:[N]\times [N]\to \{0,1\}$

To notorycznie trudny problem. Jeśli chodzi o parametry, które chcesz, wydaje mi się, że rozwiązał je Bourgain. Zobacz tutaj: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Ta odpowiedź opiera się na pomyśle Dany w jej powyższej odpowiedzi.

Myślę, że można zbudować taką matrycę przy użyciu stratnych kondensatorów z dwóch źródeł. Napraw i powiedz N = 2 n . Załóżmy, że bezpośredniej funkcji f ( x , y ) , które wykonuje jakiekolwiek dwa niezależne źródła losowych ( X , Y ) , z których każdy o długości n i o min entropia najmniej k = n ( 1 / 2 - δ ) i generuje sekwencję z n ′ = n /$\delta = 0.001$$N=2^n$$f(x,y)$$(X, Y)$$n$$k = n(1/2 - \delta)$$n' = n/2$Bity, które jest -Zamknij do rozkładu min entropii co najmniej k ' = n ( 1 / 2 - 3 δ ) . Myślę, że można użyć standardowych argumentów probabilistycznych, aby pokazać, że funkcja losowa spełnia te właściwości (z przytłaczającym prawdopodobieństwem), jeśli 2 k > k ′ + log ( 1 / ϵ ) + O ( 1 ) . Argument probabilistyczny powinien być podobny do tego, który zastosowano w poniższym artykule dla bezstratnych skraplaczy i bardziej ogólnych przewodników:$\epsilon$$k'=n(1/2-3\delta)$$2k > k'+\log(1/\epsilon)+O(1)$

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Przewodniki losowości i ciągłe rozszerzanie poza barierę stopnia / 2

W naszym przypadku ustawiamy , więc jesteśmy pewni istnienia funkcji, której potrzebujemy. Teraz, opisany przedstawia argumentów uśredniania że istnieje n ' -bitowy ciąg z takich, że liczba ( x , y ), z F ( x , y ) = oo co najmniej 2 1,5 n . Załóżmy, że znasz takie z i napraw je (możesz wybrać dowolne $\epsilon = 2^{-k'}$$n'$$z$$(x,y)$$f(x,y)=z$$2^{1.5 n}$$z$$z$jeśli dodatkowo wiesz, że twoja funkcja mapuje w pełni jednolity rozkład na rozkład, który jest -close na jednolity). Teraz zidentyfikuj wpisy swojej macierzy N × N według możliwości ( x , y ) i umieść 1 w pozycji ( x , y ) iff f ( x , y ) = z . Przez nasz wybór Z , to matryca zawiera co najmniej 2 1,5 $O(2^{-n/2})$$N \times N$$(x,y)$$1$$(x,y)$$f(x,y)=z$$z$$2^{1.5n}$ te.

Teraz weź dowolną submatrix i niech X , Y będą równomiernymi rozkładami odpowiednio na wybranych wierszach i kolumnach. Po wybraniu f wiemy, że f ( X , Y ) jest ϵ -bliskie do posiadania min-entropii k ′ . Dlatego jeśli wybieramy równomiernie losowy wpis submatrix, prawdopodobieństwo posiadania 1 wynosi co najwyżej 2 - k ′ + ϵ ≤ 2 - k ′ + $2^k \times 2^k$$X, Y$$f$$f(X,Y)$$\epsilon$$k'$$1$$2^{-k'}+\epsilon\leq 2^{-k'+1}$. Oznacza to, że masz maksymalnie w submatrix, zgodnie z życzeniem.$2^{2k-k'+1} = O(2^{n/2 + \delta})$

Oczywiście wymyślenie wyraźnego pożądanymi parametrami (w szczególności prawie optymalną długością wyjściową) jest bardzo trudnym zadaniem i jak dotąd taka funkcja nie jest znana.$f$