Koefisien Fourier Fungsi Boolean dijelaskan oleh Sirkuit Kedalaman Terikat dengan gerbang AND OR dan XOR

Biarkan menjadi fungsi Boolean dan mari kita pikirkan f sebagai fungsi dari hingga \ {-1,1 \} . Dalam bahasa ini, ekspansi Fourier dari f hanyalah perluasan dari f dalam hal monomial bebas persegi. ( 2 ^ monomial ini membentuk dasar ruang fungsi nyata pada \ {- 1,1 \} ^ n . Jumlah kuadrat dari koefisien hanya 1 sehingga f mengarah ke distribusi probabilitas pada monomial bebas persegi. Sebut distribusi ini distribusi-F.$f$$\{-1,1\}^n$$\{ -1,1 \}$$2^n$$\{-1,1\}^n$$1$$f$

Jika f dapat dijelaskan oleh rangkaian kedalaman terbatas dari ukuran polinomial maka kita tahu dengan teorema Linial, Mansour dan Nisan bahwa distribusi F terkonsentrasi pada monomial ukuran $\text{polylog } n$ hingga berat hampir secara eksponensial-kecil. Ini berasal dari Hastad switching lemma. (Bukti langsung akan sangat diinginkan.)

Apa yang terjadi ketika kita menambahkan gerbang mod 2? Salah satu contoh untuk dipertimbangkan adalah fungsi $IP_{2n}$ pada variabel $2n$ yang digambarkan sebagai produk dalam mod 2 dari variabel n pertama dan variabel n terakhir. Di sini distribusi-F adalah seragam.

Pertanyaan : Apakah distribusi-F dari fungsi Boolean dijelaskan oleh ukuran polinomial kedalaman terbatas DAN, ATAU, sirkuit MOD $_2$ terkonsentrasi (hingga kesalahan superpolynomially kecil) pada $o(n)$ "level"?

Komentar :

1. Salah satu jalan yang mungkin ke sebuah counterexample adalah dengan "merekatkan entah bagaimana" berbagai IP $_2k$ pada set variabel yang terpisah tetapi saya tidak melihat bagaimana melakukannya. Mungkin orang harus melemahkan pertanyaan dan memungkinkan menetapkan beberapa bobot pada variabel, tetapi saya juga tidak melihat cara yang jelas untuk melakukannya. (Jadi merujuk pada dua hal ini juga merupakan bagian dari apa yang saya tanyakan.)

2. Saya akan berspekulasi bahwa jawaban positif untuk pertanyaan, (atau untuk variasi yang berhasil) akan berlaku juga ketika Anda mengizinkan gerbang mod $_k$ . (Jadi mengajukan pertanyaan dimotivasi oleh hasil ACC mengesankan baru-baru ini dari Ryan Williams.)

3. Untuk UTAMA, distribusi-F adalah besar (1 / poli) untuk setiap "level".

Seperti yang ditunjukkan oleh Luca, jawaban untuk pertanyaan yang saya ajukan adalah "tidak". Pertanyaan yang tersisa adalah mengusulkan cara-cara untuk menemukan properti distribusi F fungsi Boolean yang dapat dijelaskan oleh AND OR dan gerbang mod 2 yang tidak digunakan bersama oleh MAJORITY.

Upaya untuk menyimpan pertanyaan dengan membicarakan fungsi MONOTONE:

Pertanyaan : Apakah distribusi-F dari fungsi MONOTONE Boolean dijelaskan oleh ukuran polinomial kedalaman terbatas DAN, ATAU, sirkuit MOD terkonsentrasi (hingga kesalahan superpolynomially kecil) pada "level"?$_2$$o(n)$

Kami dapat berspekulasi bahwa kami bahkan dapat mengganti dengan sehingga contoh tandingan untuk versi yang kuat ini dapat menarik. $o(n)$$\text{polylog} (n)$

Gil, apakah sesuatu seperti ini akan menjadi contoh tandingan?

Biarkan menjadi sedemikian rupa sehingga , dan anggap input bit sebagai pasangan mana adalah string m-bit dan adalah integer dalam kisaran ditulis dalam biner.n = m + log m n ( x , i ) x ( x 1 , ... , x m ) i 1 , ... , $m$$n=m+\log m$$n$$(x,i)$$x$$(x_1,\ldots ,x_m)$$i$$1,\ldots,m$

Kemudian kita mendefinisikan$f(x,i):= x_1 \oplus \cdots \oplus x_i$

Sekarang untuk setiap fungsi f () memiliki korelasi dengan karakter Fourier , dan "level i" memiliki setidaknya fraksi massa. (Sebenarnya lebih, tetapi ini sudah cukup)1 / m x 1 ⊕ ⋯ ⊕ x i 1 / m $i=1,\ldots,m$$1/m$$x_1 \oplus \cdots \oplus x_i$$1/m^2$

f () dapat diwujudkan dalam kedalaman-3: letakkan semua XOR dalam satu lapisan, dan kemudian lakukan "seleksi" dalam dua lapisan AND, OR dan NOT (tidak menghitung TIDAK sebagai menambah kedalaman, seperti biasa).