Apakah mungkin untuk membangun sebuah eksplisit 0 / 1 -matrix dengan N 1,5 yang seperti bahwa setiap N 0,499 × N 0,499 submatrix mengandung kurang dari N 0,501 orang?
Atau mungkin dimungkinkan untuk membuat set hitting yang eksplisit untuk properti tersebut.
Sangat mudah untuk melihat bahwa matriks acak memiliki properti ini dengan probabilitas secara eksponensial mendekati . Juga, expander pencampuran lemma tidak cukup untuk mendapatkan sifat ini.
Saya kira generator pseudorandom yang mengelabui persegi kombinatorial dapat membantu di sini, tetapi mereka dirancang untuk distribusi seragam dan saya pada dasarnya membutuhkan sini.
Jawaban:
Apa yang Anda cari adalah ekstraktor satu-bit untuk dua sumber independen: fungsi , sehingga, asalkan X, Y adalah variabel acak dengan min-entropi 0,499 * log (N), E (X, Y) hampir seimbang.E: [ N] × [ N] → { 0 , 1 }
Ini masalah sulit yang terkenal. Untuk parameter yang Anda inginkan, saya percaya itu diselesaikan oleh Bourgain. Lihat di sini: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf
sumber
Jawaban ini didasarkan pada ide Dana dalam jawabannya di atas.
Saya pikir Anda dapat membangun matriks seperti itu menggunakan kondensor lossy dua sumber. Perbaiki dan katakan N = 2 n . Misalkan Anda memiliki fungsi eksplisit f ( x , y ) yang mengambil dua sumber independen acak ( X , Y ) , masing-masing panjang n dan memiliki min-entropi setidaknya k = n ( 1 / 2 - δ ) dan output berurutan dari n ′ = n / 2δ= 0,001 N= 2n f( x , y) (X,Y) n k=n(1/2−δ) n′=n/2 bit yang -dekat dengan distribusi dengan min-entropi setidaknya k ' = n ( 1 / 2 - 3 δ ) . Saya pikir Anda dapat menggunakan argumen probabilistik standar untuk menunjukkan bahwa fungsi acak memenuhi sifat-sifat ini (dengan probabilitas luar biasa) jika 2 k > k ′ + log ( 1 / ϵ ) + O ( 1 ) . Untuk argumen probabilistik harus serupa dengan apa yang digunakan dalam makalah berikut untuk kondensor lossless dan konduktor yang lebih umum:ϵ k′=n(1/2−3δ) 2k>k′+log(1/ϵ)+O(1)
M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Konduktor Keacakan dan Ekspansi Derajat Konstan Melampaui Derajat / 2 Penghalang
Dalam kasus kami, kami menetapkan , jadi kami yakin tentang keberadaan fungsi yang kami butuhkan. Sekarang, argumen rata-rata menunjukkan bahwa ada string n ′ -bit z sedemikian sehingga jumlah ( x , y ) dengan f ( x , y ) = z setidaknya 2 1,5 n . Misalkan Anda tahu z seperti itu dan memperbaikinya (Anda dapat memilih sembarang zϵ=2−k′ n′ z (x,y) f(x,y)=z 21.5n z z jika Anda juga tahu bahwa fungsi Anda memetakan distribusi yang sepenuhnya seragam ke distribusi yang dekat dengan seragam). Sekarang mengidentifikasi entri dari Anda N × N matriks dengan kemungkinan ( x , y ) dan menempatkan 1 pada posisi ( x , y ) jika dan hanya jika f ( x , y ) = z . Dengan pilihan z kita , matriks ini memiliki setidaknya 2 1,5 nO(2−n/2) N×N (x,y) 1 (x,y) f(x,y)=z z 21.5n yang
sumber