Paritas dan

19

Paritas dan seperti kembar yang tidak terpisahkan. Atau begitulah tampaknya selama 30 tahun terakhir. Mengingat hasil Ryan, akan ada minat baru di kelas-kelas kecil. $AC^0$

Furst Saxe Sipser ke Yao ke Hastad semuanya adalah pembatasan paritas dan acak. Razborov / Smolensky adalah perkiraan polinomial dengan paritas (ok, gerbang mod). Aspnes et al menggunakan derajat lemah pada paritas. Lebih lanjut, Allender Hertrampf dan Beigel Tarui akan menggunakan Toda untuk kelas kecil. Dan Razborov / Beame dengan pohon keputusan. Semua ini jatuh ke keranjang paritas.

1) Apa masalah alami lainnya (selain dari paritas) yang dapat ditunjukkan secara langsung untuk tidak berada dalam ? $AC^0$

2) Adakah yang tahu tentang pendekatan yang berbeda secara drastis untuk batas bawah pada AC ^ 0 yang telah dicoba?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
sumber

13

Hasil Benjamin Rossman pada lowerbound untuk k-klik dari STOC 2008. $AC^0$

Referensi:

Paul Beame, " A Switching Lemma Primer ", Laporan Teknis 1994.
Benjamin Rossman, " Pada Kompleksitas Kedalaman Konstan dari k-Clique ", STOC 2008.

Kaveh
sumber

Bukankah Rossman digolongkan oleh primer Beame yang juga memiliki klik di dalamnya? Argumennya lebih rumit, tentu saja.

V Vinay

@V Vinay: dapatkah Anda memberikan tautan ke artikel Paul Beame?

Kaveh

4

Hasil Rossman menunjukkan bahwa -clique tidak dapat dihitung dengan sirkuit ukuran kedalaman konstan . Perhatikan bahwa konstanta dalam eksponen tidak bergantung pada kedalaman rangkaian, yang mana ia meningkatkan pada batas bawah Beame's .

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth

@Srikanth, saya pikir V Vinay mengatakan Beame memiliki hasil yang lebih baru tetapi saya tidak dapat menemukannya di halamannya. Terima kasih atas klarifikasi.

Kaveh

1

Srikanth benar tentang batas. Kaveh, bukan kertas baru; Saya menggunakan "digolongkan" dalam arti bahwa saya telah mendaftarkan Beame dalam pertanyaan saya dan karenanya menyadari adanya klik yang lebih rendah.

V Vinay

12

Ada pendekatan "top-down" oleh Håstad, Jukna dan Pudlák, seperti yang dilakukan dalam makalah mereka Batas atas-bawah bawah untuk sirkuit tiga kedalaman . Sayangnya kami sejauh ini belum dapat memperluas pendekatan ke kedalaman yang lebih tinggi.

Kristoffer Arnsfelt Hansen
sumber

Iya. Saya pikir Anda punya makalah yang dipengaruhi oleh pendekatan ini?

V Vinay

10

1) Yang pertama muncul di benak saya adalah MAYORITAS. Anda dapat membuktikan bahwa itu tidak ada di dengan teknik yang sama. Lihat tesis Håstad untuk detailnya. $AC^{0}$

2) Pendekatan topologis, sekali lagi hanya bekerja untuk sirkuit tiga kedalaman, diusulkan oleh Kriegel dan Waack .

Alessandro Cosentino
sumber

2

Mayoritas adalah hal yang sama sebenarnya. Saya seharusnya menyebutkannya. Juga, ada sebuah makalah oleh Boppana tentang Mayoritas di pertengahan 80-an.

V Vinay

8

Dua metode "klasik" lainnya adalah metode bottleneck Haken dan metode fusi Karchmer (dinamakan demikian oleh Avi Wigderson), keduanya jauh lebih mudah untuk diterapkan dalam pengaturan monoton.

Yuval Filmus
sumber

Paritas dan

Jawaban: