Apakah semua fungsi yang bobot fouriernya terkonsentrasi pada set berukuran kecil yang dihitung oleh sirkuit AC0?

Apakah semua fungsi yang Fourier berat terkonsentrasi pada set berukuran kecil (atau istilah dengan tingkat rendah) dihitung dengan sirkuit? $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
sumber

Pertanyaan ini kedengarannya menarik, meskipun saya tidak memiliki latar belakang dalam analisis fourier. Saya akan sangat menghargai referensi ke literatur terkait.

Markus

@Markus: buku ini 2.0 oleh Ryan O'Donnell adalah referensi yang bagus: contrib.andrew.cmu.edu/ ~ryanod

Alessandro Cosentino

hampir kebalikan dari Linial, Mansour, Nissan 1993 ? Hasil aaronsons, kontra-sampel untuk generalisasi Linial-Nissan tampaknya dekat? tetapi saya harus ada cara untuk menggeneralisasi hasil tahun 1993 entah bagaimana ... mungkin dalam cara yang besar ....

vzn

ide lain yang mirip bukannya AC ^ 0, lebih sulit untuk dibantah, akan menjadi kedalaman tidak terbatas tetapi total gerbang gerbang terbatas dibatasi oleh beberapa "kecil" fungsi katakanlah polinomial dll ...? juga afaik hubungan antara sirkuit monoton dan koefisien fourier tidak begitu terkenal ...?

vzn

lihat juga kemerdekaan polylogaritmik membodohi sirkuit AC ^ 0 oleh braverman

vzn

Jawaban:

Tidak. Pertimbangkan fungsi berikut pada : $\{0,1\}^n$ Jelas fungsi ini sulit untuk AC⁰. Di sisi lain, fungsinya hampir konstan, sehingga hampir semua spektrum Fouriernya ada di level pertama.

f (x) = x_{0} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1}) .

$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$

Jika Anda ingin sampel tandingan seimbang, pertimbangkan

g (x) = x_{0} \oplus [x_{1} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1})] .

$g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1})\right].$

x_{0}

$x_0$

Yuval Filmus
sumber

Apakah Anda memiliki contoh kuat di mana fungsi tidak dapat diperkirakan dalam AC0?

KIA

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

A C^{0}

$AC^0$

@Arul A Tingkat Fourier terdiri dari semua koefisien Fourier yang terkait dengan set ukuran tertentu. Kami menganggap mereka sebagai yang dipesan dalam urutan ukuran yang meningkat. Adapun mengapa fungsi ini sulit untuk AC0, ini adalah latihan. Petunjuk: paritas sulit untuk AC0.

Yuval Filmus

Ada beberapa cara untuk memahami pertanyaan sesuai dengan makna tepat "ukuran kecil" dan "berkonsentrasi."

$1-o(1)$ $S$ $1-o(1)$ ${\rm AC^0}$

2) Ada teorema Bourgain bahwa jika konsentrasinya jauh di atas fungsi mayoritas maka fungsinya kira-kira adalah Junta, dan karenanya tergantung pada variabel O (1).

$\hat f^2(S)$ $AC^0$ ${\rm polylog} (n)$

$O(\log n)$ $AC^0$

$O(polylog (n))$ $n^{polylog (n)}$

Gil Kalai
sumber