Katakanlah kita memiliki fungsi Boolean dan kami menerapkan pembatasan -random pada . Selain itu, katakan bahwa pohon keputusan yang menghitung menyusut ke ukuran sebagai akibat dari pembatasan acak. Apakah ini menyiratkan bahwa memiliki pengaruh total yang sangat rendah?
9
Jawaban:
Klaim: Jika -random pembatasan f memiliki pohon keputusan ukuran O ( 1 ) (dengan harapan), maka pengaruh total dari f tersebut adalah O ( δ - 1 ) .δ f O ( 1 ) f O ( δ- 1)
Sketsa bukti: Berdasarkan definisi pengaruh yang kita miliki . Mari kita beri batas atas Pr x , i [ f ( x ) ≠ f ( x + e i ) ] dengan terlebih dahulu menerapkan pembatasan δ , lalu memilih i ∈sayan f( f) = n ⋅ Prx , saya[ f( x ) ≠ f( x + esaya) ] Prx , saya[ f( x ) ≠ f( x + esaya) ] δ di antara koordinat yang tersisa, dan memperbaiki secara acak segala sesuatu kecuali untuk x i .i ∈ [ n ] xsaya
Sekarang, jika restriksi mengurangi pohon keputusan dari f ke ukuran O ( 1 ) , maka khususnya δ- restriksi f tergantung pada r = O ( 1 ) yang terkoordinasi. Mari kita sekarang memilih satu koordinat acak yang tidak tetap (di antara δ n ), dan perbaiki yang lainnya secara acak. Karena δ- restriksi f bergantung pada paling banyak r koordinat, kita mendapatkan fungsi (pada satu bit) yang tidak konstan dengan probabilitas paling banyak rδ f O ( 1 ) δ f r = O ( 1 ) δn δ f r . Oleh karena itusayanf(f)=n⋅Prx,i[f(x)≠f(x+ei)]≤rrδn , seperti yang dipersyaratkan.sayan f( f) = n ⋅ Prx , saya[ f( x ) ≠ f( x + esaya) ] ≤ rδ
Catatan: Klaim di atas ketat dengan mengambil fungsi paritas pada bit .O ( 1 / δ)
sumber