Pembatasan acak dan koneksi ke pengaruh total fungsi Boolean

9

Katakanlah kita memiliki fungsi Boolean f:{1,1}n{1,1} dan kami menerapkan pembatasan δ -random pada f . Selain itu, katakan bahwa pohon keputusan T yang menghitung f menyusut ke ukuran HAI(1) sebagai akibat dari pembatasan acak. Apakah ini menyiratkan bahwa f memiliki pengaruh total yang sangat rendah?

Amit Levi
sumber
adalah konstanta antara 0 dan 1 dan tidak bergantung pada n? δ
Kaveh
1
Iya. Memang . δ[0,1]
Amit Levi
1
Saya tidak yakin apakah itu yang Anda cari, tetapi oleh lemma switching, jika suatu fungsi dapat diwakili oleh DNF lebar-kecil, maka whp itu akan menyusut ke pohon keputusan dengan ukuran konstan. DNF lebar kecil memiliki pengaruh total rendah, dan seseorang dapat mengekspresikan pohon keputusan melalui DNF, jadi secara moral tampaknya inilah masalahnya.

Jawaban:

4

Klaim: Jika -random pembatasan f memiliki pohon keputusan ukuran O ( 1 ) (dengan harapan), maka pengaruh total dari f tersebut adalah O ( δ - 1 ) .δfHAI(1)fHAI(δ-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 sayanf(f)=nPrx,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 .saya[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δfHAI(1)δfr=HAI(1)δnδfr . Oleh karena itusayanf(f)=nPrx,i[f(x)f(x+ei)]rrδn , seperti yang dipersyaratkan.sayanf(f)=nPrx,saya[f(x)f(x+esaya)]rδ

Catatan: Klaim di atas ketat dengan mengambil fungsi paritas pada bit .HAI(1/δ)

Igor Shinkar
sumber