Pada status kemampuan belajar di dalam

Saya mencoba memahami kompleksitas fungsi yang dapat diekspresikan melalui ambang pintu dan ini membawa saya ke . Secara khusus, saya tertarik dengan apa yang saat ini diketahui tentang pembelajaran di dalam , karena saya bukan ahli di bidang ini. $\mathsf{TC}^0$ $\mathsf{TC}^0$

Apa yang saya temukan sejauh ini adalah:

Semua dapat dipelajari dalam waktu quasipolynomial bawah distribusi seragam melalui Linial-Mansour-Nisan . $\mathsf{AC}^0$
Kertas mereka juga menunjukkan bahwa keberadaan mencegah fungsi pseudorandom generator yang belajar, dan ini, ditambah dengan hasil kemudian Naor-Reingold yang anak mengatakan PRFGs, menunjukkan bahwa mewakili batas learnability (setidaknya dalam PAC -merasakan) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Ada 2002 kertas dengan Jackson / Klivans / Servedio yang dapat belajar sebuah fragmen dari (dengan paling gerbang mayoritas polylogarithmic). $\mathsf{TC}^0$

Saya sudah melakukan google scholaring biasa, tetapi saya berharap kebijaksanaan kolektif cstheory mungkin memiliki jawaban yang lebih cepat:

Apakah yang saya gambarkan sebagai bagian dari seni untuk pemahaman kita tentang kompleksitas pembelajaran (dalam hal mana kelas-kelas membuat sandwich pelajar yang efisien)? Dan adakah survei / referensi yang bagus yang memetakan kondisi lanskap saat ini?

cc.complexity-theory reference-request cr.crypto-security lg.learning boolean-functions Suresh Venkat
sumber

+1 pertanyaan yang bagus. Bukankah Lance punya posting blog terkait beberapa waktu lalu?

Kaveh

Maksud Anda yang ini (posting tamu oleh Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/…

Suresh Venkat

Mungkin yang ini: blog.computationalcomplexity.org/2013/08/...

Suresh Venkat

Masuk akal bahwa ada generator pseudorandom di NC0 .

$\:$ (Secara khusus, saya merasa sangat tidak mungkin bahwa generator pseudorandom diketahui mencegah pembelajaran.)

$\;\;\;$ Di sisi lain, keberadaan peta

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$ untuk fungsi pseudorandom keluarga

tidak mencegah pembelajaran.

F

$F$

Linial-Mansour-Nisan menunjukkan bahwa

dapat dipelajari di bawah distribusi seragam dalam waktu quasipolynomial . Kharitinov menunjukkan bahwa jika kuasipolinomial ditingkatkan menjadi polinomial, itu akan menghasilkan algoritma waktu sub-eksponensial untuk memfaktorkan bilangan bulat Blum.

{AC}^{0}

$\text{AC}^0$

Robin Kothari

Jawaban:

Hal utama yang hilang dari daftar Anda adalah kertas 2006 yang indah dari Kliva dan Sherstov . Mereka menunjukkan di sana bahwa pembelajaran PAC bahkan sirkuit ambang kedalaman-2 sama sulitnya dengan memecahkan masalah vektor terdekat.

Scott Aaronson
sumber

Apa waktu berjalan tercepat yang diketahui untuk mempelajari sirkuit LTF seperti itu? (atau apa pun di dalam

)

T C^{0}

$TC^0$

gradstudent

Kedalaman-2 TC0 mungkin tidak dapat dipelajari PAC dalam waktu subeksponensial atas distribusi seragam dengan akses oracle acak. Saya tidak tahu referensi untuk ini, tapi inilah alasan saya: Kita tahu bahwa paritas hanya bisa dipelajari, dalam arti bahwa kelas fungsi paritas dapat dipelajari dengan sendirinya, tetapi begitu Anda melakukan apa saja untuk itu (seperti seperti menambahkan sedikit noise acak), itu tidak lagi bisa dipelajari. Tapi kedalaman-2 TC0 cukup kuat untuk mewakili semua fungsi paritas dan cukup kuat untuk mewakili versi paritas yang terganggu, jadi saya pikir aman untuk menebak bahwa kedalaman-2 TC0 tidak dapat dipelajari PAC.

Namun, paritas dan paritas berisik dapat dipelajari dalam waktu polinomial jika kita diberi oracle keanggotaan. Jadi mungkin menarik untuk memeriksa apakah kedalaman-2 TC0 dapat dipelajari menggunakan oracle keanggotaan. Saya tidak akan benar-benar terkejut jika jawabannya adalah ya. Di sisi lain, saya ragu bahwa -depth TC0 dapat dipelajari dengan pertanyaan keanggotaan. Mungkin baik untuk memulai dengan AC0 [6] (atau bahkan AC0 [2]) dan pergi dari sana. $O(1)$

pangsit mobius
sumber