Beigel-Tarui transformasi cricuit ACC

14

Saya membaca lampiran tentang batas bawah ACC untuk NEXP dalam buku Komputasi Kompleksitas Arora dan Barak . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Salah satu lemmas kunci adalah transformasi dari sirkuit untuk polinomial multilinear atas bilangan bulat dengan gelar polylogarithmic dan koefisien quasipolynomial, atau ekuivalen , kelas sirkuit S Y M + , yang merupakan kelas dari kedalaman dua sirkuit dengan gerbang AND yang banyak secara kuantitatif pada level dasarnya dengan fan-in polylogarithmic, dan gerbang simetris pada level atas.ACC0SYM+

Dalam lampiran buku teks, transformasi ini memiliki tiga langkah, dengan asumsi bahwa set gerbang terdiri dari OR, mod , mod 3 , dan konstanta 1 . Langkah pertama adalah untuk mengurangi fan-in dari gerbang OR ke urutan polylogarithmic.231

Menggunakan Valiant-Vazirani Isolasi Lemma, penulis memperoleh yang diberi gerbang OR lebih masukan dari bentuk O R ( x 1 , . . . , X 2 k ) , jika kita memilih h menjadi berpasangan fungsi hash independen , dari [ 2 k ] ke { 0 , 1 } , lalu untuk sembarang nol x { 0 , 1 } 10 k ) akan menyatakan bahwa Σ i :2kOR(x1,...,x2k)h[2k]{0,1} , dengan probabilitas setidaknya1/(x{0,1}2k1/(10k).Σi:h(i)=1ximod 2

Bukankah kemungkinan setidaknya 1 / 2 ? Tampaknya 1 / 10 k adalah batas bawah yang lemah.Σi:h(i)=1ximod 21/21/10k

Langkah kedua adalah pindah ke gerbang aritmatika dan mendorong multiplikasi ke bawah. Pada langkah ini, kita akan mengubah sirkuit Boolean dengan string input biner yang diberikan ke sirkuit aritmatika dengan input integer.

Di sini mereka mencatat bahwa diganti dengan 1 - x 1 x 2x k , dan M O D p ( x 1 , . . . , X k ) diganti dengan ( Σ i = 1 , . . . , k x i ) p -OR(x1,...,xk)1x1x2xkMODp(x1,...,xk) menggunakan Teorema Kecil Fermat.(Σi=1,...,kxi)p1

Mengapa penggantian ini memberikan S Y yang setarasirkuit M + yang?SYM+

sungguh-sungguh
sumber
3
Saya tidak mengerti ungkapan yang mengikuti "dengan probabilitas setidaknya 1 / (10k) itu akan menyatakan bahwa ...." Apakah Anda kehilangan tanda sama dengan? Juga, dapatkah Anda mengutip nomor halaman tempat bukti ini muncul?
Robin Kothari

Jawaban:

10

Bukankah probabilitas setidaknya 1/2? Tampaknya 1 / ( 10 k ) adalah batas bawah yang lemah.Σi:h(i)=1ximod 2=11/(10k)

Sebenarnya jawabannya adalah tidak. (Ini akan menjadi yang memegang dengan probabilitas setidaknya 1 / 2 - ε , jika kita bekerja dengan ε -biased keluarga hash, dan memang menggunakan ε hash -biased fungsi memberikan cara untuk meningkatkan parameter konstruksi. Tetapi kemandirian berpasangan belum tentu ε- suit.)Σi:h(i)=1ximod 2=11/2εεεε

Sepertinya mereka kehilangan satu langkah tambahan di sini. Untuk menerapkan Valiant-Vazirani secara langsung, Anda juga harus secara acak memilih rentang fungsi hash. Daripada memilih acak berpasangan-independen , tampaknya Anda harus memilih acak { 2 , ... , k + 1 } dan kemudian memilih acak berpasangan-independen h : [ 2 k ] { 0 , 1 } h:[2k]{0,1}{2,,k+1}h:[2k]{0,1}. (Di sini saya sengaja menggunakan pernyataan Arora-Barak dari Valiant-Vazirani, ditemukan pada halaman 354.) Let menjadi jumlah x i = 1 . Valiant-Vazirani mengatakan bahwa ketika Anda memilih sedemikian rupa sehingga 2 - 2s 2 - 1 , maka probabilitas bahwa Σ i : h ( i ) = 1 x i = 1 (lebih dari bilangan bulat!) Setidaknya 1 / 8 .sxi=122s21Σi:h(i)=1xi=11/8

Jadi dengan memilih acak dan memilih acak berpasangan independen h : [ 2 k ] { 0 , 1 } , maka Anda memiliki probabilitas setidaknya 1 / ( 8 k ) bahwa Σ i : h ( i ) = 1 x i mod  2 = 1 . Untuk mensimulasikan pilihan acak di sirkuit, Anda bisa mengambil O R dari semua kemungkinan h:[2k]{0,1}1/(8k)Σi:h(i)=1ximod 2=1OR (jumlah mereka adalah logaritmik dalam , setelah semua), sehingga probabilitas keberhasilan menjadi minimal 1 / 8 lagi. Jadi daripada memilikifungsi hash O ( k log s ) dengan rentang { 0 , 1 } , Anda akan menginginkan O ( k ) set fungsi hash yang berbeda (masing-masing set memiliki rentang yang berbeda), dengan O ( log s2k1/8O(klogs){0,1}O(k)fungsi hash ) di setiap set.O(logs)

Mengapa penggantian ini memberikan sirkuit SYM + yang setara?

Sirkuit SYM dari AND (yaitu, SYM +) ukuran pada dasarnya setara dengan memiliki polinomial multivarian h : { 0 , 1 } n{ 0 , ... , K } dengan paling banyak monomial K , tabel pencarian g : { 0 , ... , K } { 0 , 1 } , dan menghitung g ( h ( x 1 , ... , x n )Kh:{0,1}n{0,,K}Kg:{0,,K}{0,1}g(h(x1,,xn))fgh

Ryan Williams
sumber