Menipu fungsi simetris yang sewenang-wenang

17

Distribusi dikatakan ϵ -membodoh fungsi f jika | E x U ( f ( x ) ) - E x D ( f ( x ) ) | ϵ . Dan dikatakan menipu kelas fungsi jika menipu setiap fungsi di kelas itu. Hal ini diketahui bahwa ε ruang -biased menipu kelas paritas lebih himpunan bagian. (lihat Alon-Goldreich-Hastad-PeraltaDϵf|ExU(f(x))ExD(f(x))|ϵ

ϵuntuk beberapa konstruksi ruang yang bagus). Pertanyaan yang ingin saya tanyakan adalah generalisasi dari ini ke fungsi simetris yang sewenang-wenang.

Pertanyaan: Misalkan kita mengambil kelas fungsi simetris yang sewenang-wenang atas beberapa subset, apakah kita memiliki distribusi (dengan dukungan kecil) yang membodohi kelas ini?

Beberapa pengamatan kecil:

  • Cukup untuk mengelabui ambang yang pasti ( adalah 1 jika dan hanya jika x memiliki k yang tepat di antara indeks dalam S ). Setiap distribusi yang ε -fools ini ambang batas yang sebenarnya akan n ε menipu semua fungsi simetris lebih n bit. (Ini karena setiap fungsi simetris dapat ditulis sebagai kombinasi linear nyata dari ambang yang tepat ini di mana koefisien dalam kombinasi adalah 0 atau 1. Linearitas harapan kemudian memberi kita apa yang kita inginkan) Argumen serupa juga bekerja untuk ambang umum ( Th S k ( xEThkS(x)xkSϵnϵn

    adalah 1 jika dan hanya jika x memiliki setidaknya k di antara indeks dalam S )ThkS(x)xkS

  • Ada konstruksi eksplisit distribusi dengan dukungan melalui PRG Nisan untuk LOGSPACE .nO(logn)

  • Sewenang-wenang -biased ruang tidak akan bekerja. Sebagai contoh jika S adalah himpunan semua x sehingga jumlah yang di x adalah non-nol mod 3, ini sebenarnya ε -biased untuk sangat kecil ε (dari hasil Arkadev Chattopadyay ). Namun yang jelas ini tidak menipu fungsi MOD3.ϵSxϵϵ

Submasalah yang menarik mungkin sebagai berikut: misalkan kita hanya ingin mengelabui fungsi simetris atas semua indeks , apakah kita memiliki ruang yang bagus? Dengan pengamatan di atas, kita hanya perlu untuk menipu fungsi threshold lebih -bits, yang hanya keluarga n + 1 fungsi. Dengan demikian orang dapat memilih distribusi dengan kekerasan. Tetapi apakah ada contoh ruang yang lebih bagus yang mengelabui Th [ n ] k untuk setiap k ?nn+1Thk[n]k

Ramprasad
sumber
Mungkin komentar ini bisa membantu. Dugaan Linial dan Nisan baru-baru ini diselesaikan oleh Mark Braverman. Judul makalah ini adalah "Kemandirian polylogaritmik menipu sirkuit AC ^ 0". cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf
Mirmojtaba Gharibi

Jawaban:

11

Ya, solusi umum untuk masalah ini baru-baru ini diberikan oleh Parikshit Gopalan, Raghu Meka, Omer Reingold, dan David Zuckerman, lihat Pseudorandom Generator untuk Bentuk Combinatorial .

Makalah itu menangani pengaturan yang bahkan lebih umum, di mana generator menghasilkan log m- bit blok, yang kemudian diumpankan ke fungsi boolean yang sewenang-wenang, yang n keluarannya kemudian diumpankan ke fungsi simetris boolean.n logmn

Berbagai sub-kasus sudah diketahui; lihat misalnya Generator Bit Pseudorandom yang Menipu Jumlah Modular , Halfspace Fool Kemandirian Terbatas , dan Generator Pseudorandom untuk Fungsi Ambang Batas Polinomial . Yang pertama menangani jumlah modulo . Pegangan kedua dan ketiga persis tes ambang yang Anda sebutkan, namun kesalahan tidak cukup baik untuk menerapkan alasan Anda untuk mendapatkan hasil untuk setiap fungsi simetris.hal

Manu
sumber
1
Tetapi Gopalan-Meka-Reingold-Zuckerman tidak memberikan PRG yang optimal untuk kesalahan polinomial terbalik, kan? Untuk konstanta , itu adalah optimal. Meskipun demikian, terima kasih banyak untuk penunjuknya. ε
Ramprasad
Memang tidak. Secara umum itu adalah tujuan yang sulit, dan ada beberapa contoh dalam literatur di mana ketergantungan logaritmik pada tercapai. ε
Manu