Fungsi Boolean Dimana Sensitivitas Menyamakan Memblokir Sensitivitas

17

Beberapa pekerjaan pada sensitivitas vs sensitivitas blok telah ditujukan untuk memeriksa fungsi dengan kesenjangan sebesar mungkin antara s(f) dan bs(f) untuk menyelesaikan dugaan bahwa bs(f) hanya lebih besar secara polinomi dari s(f) . Bagaimana dengan arah yang berlawanan? Apa yang diketahui tentang fungsi di mana s(f)=bs(f) ?

Sepele, fungsi konstan memiliki 0=s(f)=bs(f) . Juga sepele, fungsi apa pun dengan s(f)=n juga memiliki s(f)=bs(f) . Ini tidak sepele tetapi tidak terlalu sulit untuk menunjukkan bahwa fungsi monoton apa pun juga memenuhi persamaan ini. Apakah ada kelas fungsi lain yang bagus yang memiliki s(f)=bs(f) ? Karakterisasi lengkap akan ideal. Bagaimana jika kita semakin memperkuat persyaratan menjadi s0(f)=bs0(f) dans1(f)=bs1(f) ?

Motivasi untuk pertanyaan ini hanyalah untuk mendapatkan intuisi tentang bagaimana sensitivitas berhubungan dengan memblokir sensitivitas.

Definisi

Biarkan f:{0,1}n{0,1} menjadi fungsi Boolean pada kata- n bit. Untuk x{0,1}n dan A{0,1,,n} , biarkan xA menyatakan n kata-bit yang diperoleh dari x dengan membalik bit yang ditentukan oleh A . Dalam hal A={i} , kami hanya akan menyatakan ini sebagaixi .

Kami mendefinisikan sensitivitas f pada x sebagai s(f,x)=#{i|f(xi)f(x)} . Dengan kata lain, jumlah bit dalam x yang dapat kita flip untuk membalik output f . Kami mendefinisikan sensitivitas dari f sebagai s(f)=maxxs(f,x).

Kami mendefinisikan sensitivitas blok f pada x (dinotasikan bs(f,x) ) sebagai maksimum k sehingga ada himpunan bagian yang saling terpisah B1,B2,,Bk dari {1,2,,n} seperti bahwa f(xBi)f(x) . Kami mendefinisikan sensitivitas blok darif asbs(f)=maxxbs(f,x) .

Akhirnya, kita mendefinisikan 0-sensitivitas dari f sebagai s0(f)=max{s(f,x)|f(x)=0} . Kami juga mendefinisikan 1-sensitivitas , sensitivitas 0-blok , dan sensitivitas 1-blok , dilambangkan s1(f) , bs0(f) , dan bs1(f) , masing-masing.

mhum
sumber

Jawaban:

17

Baru-baru ini, saya membuktikan bahwa s (f) = bs (f) untuk fungsi unate dan fungsi baca-sekali melalui operator Boolean AND, OR dan EXOR, dan makalah saya termasuk hasilnya diterima di TCS 2014. ( http: // dx .doi.org / 10.1007 / 978-3-662-44602-7_9 )

Anda mungkin menyerang masalah ini. Jika demikian, saya merasa menyesal, tetapi saya mulai menyerang masalah secara mandiri sebelum pertanyaan diposting. Versi awal dari makalah saya dipresentasikan pada pertemuan domestik Jepang pada bulan Desember / 2013 dan batas waktu pengiriman adalah Oktober / 2013. ( http://www.ieice.org/ken/paper/20131220DBID/eng/ )

Hiroki Morizumi
sumber
2
Hasil yang bagus. Saya berharap dapat membacanya.
mhum