Upperbound pada tingkat fungsi boolean dalam hal sensitivitasnya

Masalah terbuka yang sangat menarik dalam studi ukuran kompleksitas fungsi Boolean adalah dugaan sensitivitas vs blok sensitivitas. Untuk latar belakang tentang sensitivitas versus sensitivitas blok Anda dapat melihat posting blog berikut S. Aaronson di http://www.scottaaronson.com/blog/?p=453 .

Sepengetahuan saya, batas atas terbaik yang diketahui pada dalam hal adalah . [Kenyon, kertas Kutin] Tapi tentu saja mungkin lebih mudah untuk menghubungkan dengan beberapa ukuran kompleksitas lain dari katakan , tingkat sebagai polinomial lebih dari , yaitu ukuran dari koefisien Fourier tertinggi. $bs(f)$ $s(f)$ $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

Pertanyaannya adalah apakah batas atas terbaik yang diketahui pada dalam hal ? $\deg(f)$ $s(f)$

cc.complexity-theory reference-request fourier-analysis Mohammad Bavarian
sumber

Anda dapat menggunakan hasil Nisan-Szegedy bahwa kompleksitas pohon keputusan deterministik adalah dan Anda akan memiliki . Saya tidak tahu apakah ini yang terbaik.

D (f) \leq b s^{4} (f)

$D(f)\leq bs^4(f)$

\tilde{d e g} (f) = O (e^{4 s (f)} s^{2} (f))

$\widetilde{deg}(f)=O(e^{4s(f)} s^2(f))$

Marcos Villagra

Saya cukup yakin bahwa tidak ada yang melakukan lebih baik daripada melalui koneksi yang disebutkan Marcos. Sangat alami untuk menghubungkan s dengan bs. deg (f) secara polinomi terkait dengan sebagian besar kuantitas lainnya, misalnya D (f), bs (f), C (f), kira-kira (f), dll. Anda dapat menikmati survei Buhrman-De Wolf pada kompleksitas pohon keputusan yang mengulas langkah-langkah ini.

Andy Drucker

Saya pikir bukti Simon dari 80-an memberikan batas yang sedikit lebih baik: sesuatu seperti .

d e g (f) \leq D T (f) \leq 4^{s (f)} \cdot p o l y (s (f))

$deg(f) \le DT(f) \le 4^{s(f)}\cdot poly(s(f))$

Avishay Tal

Upperbound pada tingkat fungsi boolean dalam hal sensitivitasnya

Jawaban: