Panduan Pemula untuk Derandomisasi

17

Saya menemukan buku Pairwise Independence and Derandomization pada subjek, tetapi lebih berorientasi pada penelitian daripada berorientasi pada tutorial.

Saya baru mengenal subjek "Derandomisasi," dan karena itu, saya ingin tahu referensi mana yang harus dimulai?

Saya lebih suka yang membahas literatur dan sejarah, serta rincian teknis.

cc.complexity-theory derandomization randomized-algorithms MS Dousti
sumber
3
Buku pelajaran Arora dan Barak tentang kompleksitas komputasi mencakup derandomisasi dengan cukup baik. Apakah Anda memikirkan hal lain?
Ryan Williams
Terima kasih. Aku akan melihatnya. Saya tidak memiliki hal lain di pikiran saya. Hanya untuk membaca dan memahami beberapa makalah, saya perlu memahami derandomisasi terlebih dahulu.
MS Dousti

Jawaban:

16

Catatan dari kelas Salil Vadhan, "Pseudorandomness" , sangat bagus untuk tujuan ini. Dia menulis buku pelajaran berdasarkan ini. Versi konsep buku ini tersedia online .

arnab
sumber
tautan yang bagus. Menunggu buku ini saat terbit
Suresh Venkat
Ya, sangat dihargai.
MS Dousti
8

Saya sangat suka Pseudorandom Generator: A Primer oleh Oded Goldreich. Saya pikir ini ditulis dengan sangat baik dan mungkin pada level yang Anda inginkan. (Tidak terlalu berorientasi penelitian, tetapi masih memiliki detail teknis.)

Robin Kothari
sumber
1
Ini telah diterbitkan sebagai buku pada tahun 2010.
MS Dousti