Perkiraan derajat

EDIT (v2): Menambahkan bagian di akhir tentang apa yang saya ketahui tentang masalah.

EDIT (v3): Menambahkan diskusi tentang ambang batas di akhir.

Pertanyaan

Pertanyaan ini terutama merupakan permintaan referensi. Saya tidak tahu banyak tentang masalahnya. Saya ingin tahu apakah ada pekerjaan sebelumnya tentang masalah ini, dan jika demikian, dapatkah seseorang mengarahkan saya ke makalah yang membicarakan masalah ini? Saya juga ingin tahu batas terbaik saat ini pada tingkat perkiraan . Informasi lain apa pun juga akan dihargai (misalnya, informasi historis, motivasi, hubungan dengan masalah lain, dll.).$\textrm{AC}^0$

Definisi

Biarkan menjadi fungsi Boolean. Misalkan menjadi polinomial atas variabel hingga dengan koefisien nyata. Derajat polinomial adalah derajat maksimum di atas semua monomial. Derajat monomial adalah jumlah eksponen dari berbagai yang muncul dalam monomial itu. Misalnya .$f:\{0,1\}^n \to \{0,1\}$$p$$x_1$$x_n$$x_i$$\textrm{deg}(x_1^7x_3^2) = 9$

Suatu polinomial dikatakan sebagai -approximate if untuk semua . The tingkat -approximate dari fungsi Boolean , dinotasikan sebagai , adalah tingkat minimum yang jumlahnya banyak yang -approximates . Untuk sekumpulan fungsi, , adalah derajat minimum sehingga setiap fungsi dalam dapat -ditaksir oleh polinomial derajat paling banyak$p$$\epsilon$$f$$|f(x)-p(x)|<\epsilon$$x$$\epsilon$$f$$\widetilde{\textrm{deg}}_{\epsilon}(f)$$\epsilon$$f$$F$$\widetilde{\textrm{deg}}_{\epsilon}(F)$$d$$F$$\epsilon$$d$.

Perhatikan bahwa setiap fungsi dapat direpresentasikan tanpa kesalahan dengan derajat jumlahnya banyak. Beberapa fungsi benar-benar membutuhkan derajat polinomial untuk memperkirakan kesalahan konstan apa pun. Paritas adalah contoh dari fungsi semacam itu.$n$$n$

Pernyataan masalah

Apa itu ? (Konstanta 1/3 adalah arbitrer.)$\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$

Catatan

Saya mengalami masalah ini di koran The Quantum Query Complexity of AC0 oleh Paul Beame dan Widad Machmouchi. Mereka bilang

Juga, hasil kami tidak melakukan apa pun untuk menutup celah di batas bawah pada tingkat perkiraan fungsi AC0.

Mereka menyebutkan "masalah tingkat perkiraan AC0" dalam ucapan terima kasih mereka juga.

Jadi saya berasumsi telah ada beberapa pekerjaan pada masalah ini sebelumnya? Dapatkah seseorang mengarahkan saya ke sebuah makalah yang membicarakan masalah tersebut? Dan apa batas atas dan bawah yang paling dikenal?

Apa yang saya ketahui tentang masalah (Bagian ini ditambahkan dalam v2 pertanyaan)

Batas atas paling dikenal di yang diketahui adalah batas atas sepele . Batas bawah terbaik yang saya tahu berasal dari batas bawah Aaronson dan Shi untuk masalah perbedaan tabrakan dan elemen, yang memberikan batas bawah . (Untuk versi sangat terbatas dari , seperti formula dengan ukuran rumus, atau kedalaman-2 sirkuit dengan gerbang, kita bisa membuktikan atas terikat menggunakan kompleksitas kueri kuantum.)n ~ Ω (n2/3)AC0o(n2)o(n2)o(n$\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$$n$$\tilde{\Omega}(n^{2/3})$$\textrm{AC}^0$$o(n^2)$$o(n^2)$$o(n)$

Terkait: derajat ambang (Ditambahkan dalam v3)

Seperti yang ditunjukkan oleh Tsuyoshi dalam komentar, masalah ini terkait dengan masalah menentukan tingkat ambang . Tingkat ambang fungsi adalah tingkat minimum polinomial sehingga dan . fpf(x)=$\textrm{AC}^0$$f$$p$f ( x ) = $f(x)=1 \implies p(x)>0$$f(x)=0 \implies p(x)<0$

Batas bawah untuk tingkat ambang sekarang telah ditingkatkan oleh Sherstov. Dia menunjukkan keluarga formula baca-sekali kedalaman konstan pada variabel yang derajat ambangnya mendekati ketika kedalamannya hingga tak terhingga, yang hampir ketat karena rumus baca-sekali memiliki ambang (dan bahkan perkiraan ) derajat . Lihat http://eccc.hpi-web.de/report/2014/009/ . (Jan, 2014) nΩ($\mathrm{AC}^0$$n$O($\Omega(\sqrt{n})$$O(\sqrt{n})$

Sebuah makalah oleh Mark Bun dan Justin Thaler telah diposting di ECCC baru-baru ini (pertengahan Maret 2017) yang secara tepat menjawab pertanyaan ini: "Batas Bawah yang Hampir Optimal pada Perkiraan Tingkat AC0"

Mereka mengklaim bahwa untuk setiap , ada fungsi di sedemikian rupa sehingga , hampir menutup celah dengan batas atas sepele . Mereka mencapainya dengan metode umum untuk meningkatkan derajat perkiraan suatu fungsi dengan tingkat perkiraan sublinear, menjaga jumlah variabel kuasi-linier. Dari abstrak:f A C 0 ~ d e g 1 / 3 ( f ) = Ω $\delta > 0$$f$$\mathrm{AC}^0$O ( n $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$$O(n)$

Secara khusus, kami menunjukkan bagaimana mengubah fungsi Boolean dengan perkiraan derajat menjadi fungsi pada variabel dengan derajat perkiraan setidaknya . Khususnya, jika , maka secara polinomi lebih besar dari . Selain itu, jika dihitung oleh sirkuit Boolean ukuran polinomial dengan kedalaman konstan, maka .d F O ( n ⋅ p o l y l o g ( n ) ) D = Ω ( n 1 / 3 · d 2 / 3 ) d = n 1 - Ω ( 1 ) D d f $f$$d$$F$$O(n \cdot \mathrm{polylog}(n))$$D = Ω(n^{1/3} · d^{2/3} )$$d = n^{1−Ω(1)}$$D$$d$$f$$F$

Itu adalah pembaruan terbaru pada batas bawah masalah ini, dan ini merupakan langkah maju yang cukup signifikan. Bagian Pendahuluan dan Aplikasi dari makalah ini juga merupakan sumber referensi yang baik untuk pekerjaan sebelumnya dan masalah terkait.

Penafian: Saya belum membaca koran dengan cermat.