Seringkali, ketika kita mengambil bagian dalam konferensi TCS, kita melihat beberapa detail kecil yang kita harapkan dari penyelenggara konferensi. Dan ketika kita menyelenggarakan konferensi, kita sudah melupakannya. Karena itu pertanyaannya: Langkah kecil apa yang bisa kita ambil dengan mudah...
Saya ingin menulis survei tentang aplikasi Topologi dalam Ilmu Komputer. Saya berencana untuk membahas sejarah ide-ide topologi dalam Ilmu Komputer dan juga menyoroti beberapa perkembangan saat ini. Akan sangat membantu jika ada yang bisa memberi masukan tentang pertanyaan di bawah ini. Adakah...
Kami di TCS sering menggunakan hasil dan gagasan yang kuat dari matematika klasik (aljabar, topologi, analisis, geometri, dll.). Apa saja contoh ketika itu telah terjadi sebaliknya? Berikut adalah beberapa yang saya ketahui (dan juga untuk memberikan rasa dari jenis hasil yang saya...
Saya mencari contoh masalah dengan parametrized oleh angka k∈Nk∈Nk \in \mathbb{N} , di mana kekerasan masalahnya non-monotonik dalam kkk . Sebagian besar masalah (dalam pengalaman saya) memiliki transisi fase tunggal, misalnya kkk -SAT memiliki transisi fase tunggal dari k∈{1,2}k∈{1,2}k \in \{1,2\}...
Selama bertahun-tahun saya telah terbiasa melihat banyak teorema TCS terbukti menggunakan analisis Fourier diskrit. Transformasi Walsh-Fourier (Hadamard) berguna di hampir setiap subbidang TCS, termasuk pengujian properti, pseudorandomness, kompleksitas komunikasi, dan komputasi kuantum. Sementara...
Apa pedoman umum untuk memeriksa bukti Anda? Saya percaya ini penting bagi mahasiswa pascasarjana seperti saya. Saya sudah tahu apa yang perlu kita lakukan untuk membuktikan sesuatu, tetapi Anda harus selalu memeriksa semuanya sebelum mengirimkannya. Bahkan kepada penasihat Anda sendiri. Saya...
Latar Belakang Beberapa tahun yang lalu, ketika saya masih sarjana, kami diberi pekerjaan rumah tentang analisis diamortisasi. Saya tidak dapat menyelesaikan salah satu masalah. Saya telah menanyakannya dalam teori comp.the , tetapi tidak ada hasil yang memuaskan muncul. Saya ingat kursus TA...
Setelah mempelajari deterministic finite state automata (DFA) di tingkat sarjana, saya merasa mereka sangat dipahami. Pertanyaan saya adalah apakah ada sesuatu yang masih belum kita mengerti tentang mereka. Maksud saya bukan generalisasi DFA tetapi DFA asli yang tidak dimodifikasi yang kami...
Pertanyaan ini adalah sesuatu yang sudah lama saya tanyakan. Ketika orang menggambarkan masalah P vs NP, mereka sering membandingkan NP kelas dengan kreativitas. Mereka mencatat bahwa menyusun simfoni kualitas Mozart (analog dengan tugas NP) tampaknya jauh lebih sulit daripada memverifikasi bahwa...
Saya baru di situs ini. Pada mathoverflow ini adalah wiki komunitas, tapi saya tidak melihat cara mengaturnya di sini. Bukan pertanyaan penelitian, tapi semoga menarik bagi para ilmuwan komputer teoretis profesional. Saya seorang mahasiswa tahun ke-2 dalam teori, dan saya bertanya-tanya apa saran...
Apakah Anda tahu algoritma masuk akal yang berjalan dalam waktu polinomial dalam (Panjang input + Panjang output), tetapi yang menjalankan waktu asimtotik dalam ukuran yang sama memiliki eksponen / konstanta yang sangat besar (setidaknya, di mana batas atas terbukti pada waktu berjalan adalah dalam...
Secara luas diduga bahwa , eksponen optimal untuk perkalian matriks, sebenarnya sama dengan 2. Pertanyaan saya sederhana:ωω\omega Apa alasan yang kita miliki untuk meyakini bahwa ?ω=2ω=2\omega = 2 Saya mengetahui algoritma cepat seperti Coppersmith-Winograd, tapi saya tidak tahu mengapa ini...
Di utas Masalah utama yang belum terpecahkan dalam ilmu komputer teoritis? , Iddo Tzameret membuat komentar luar biasa berikut: Saya pikir kita harus membedakan antara masalah terbuka utama yang dipandang sebagai masalah mendasar, seperti , dan masalah terbuka utama yang akan menjadi terobosan...
Ketika merancang suatu algoritma untuk masalah baru, jika saya tidak dapat menemukan algoritma waktu polinomial setelah beberapa saat, saya mungkin mencoba membuktikannya sebagai NP-hard. Jika saya berhasil, saya sudah menjelaskan mengapa saya tidak dapat menemukan algoritma waktu polinomial....
Dengan munculnya internet (dan akal sehat) ada semakin banyak permintaan untuk penelitian akses terbuka. Beberapa peneliti (termasuk saya) merasa frustasi karena artikel-artikel penelitian yang diterbitkan oleh rekan sejawat berada di belakang paywalls. Saya mencari jurnal dan konferensi (terkait...
Algoritma genetika tidak mendapatkan banyak daya tarik dalam dunia teori, tetapi mereka adalah metode metaheuristik yang cukup baik digunakan (oleh metaheuristik maksud saya teknik yang berlaku secara umum di banyak masalah, seperti anil, keturunan gradien, dan sejenisnya). Faktanya, teknik mirip...
Baru-baru ini, ketika berbicara dengan seorang ahli fisika, saya menyatakan bahwa dalam pengalaman saya, ketika masalah yang secara naif sepertinya membutuhkan waktu eksponensial ternyata secara nontrivial berada di P atau BPP, "alasan menyeluruh" mengapa pengurangan terjadi biasanya dapat...
Tujuan dari pertanyaan ini adalah untuk mengumpulkan contoh-contoh dari ilmu komputer teoretis di mana penggunaan komputer secara sistematis sangat membantu dalam membangun dugaan yang mengarah pada teorema, memalsukan pendekatan dugaan atau bukti, membangun / memverifikasi (bagian dari)...
Alat apa yang Anda gunakan untuk menulis makalah? Dari sedikit pengalaman yang saya miliki, para ahli teori menghabiskan banyak waktu untuk menulis dan memperbaiki makalah, selain benar-benar menjadi kreatif. Yaitu, mengomunikasikan pekerjaan mereka kepada orang lain. Mungkin makalah bukan cara...
Saya telah menemukan algoritma polinomial yang memecahkan 2SAT. Saya menemukan itu mengejutkan bahwa 2SAT ada di P di mana semua (atau banyak lainnya) dari instance SAT adalah NP-Complete. Apa yang membuat masalah ini berbeda? Apa yang membuatnya sangat mudah (Lengkap-NL - bahkan lebih mudah...