Apa buku TCS terbaru yang konsepnya tersedia online?

Setelah posting Apa Buku Yang Harus Dibaca Semua Orang , saya perhatikan ada buku-buku terbaru yang draftnya tersedia online.

Sebagai contoh, entri Algoritma Approximation dari posting di atas mengutip sebuah buku 2011 (belum dipublikasikan) berjudul Desain algoritma pendekatan .

Saya pikir mengetahui karya terbaru sangat berguna bagi siapa pun yang ingin merasakan tren TCS. Ketika draft tersedia, orang dapat memeriksa buku sebelum benar-benar membelinya.

Begitu,

Apa buku TCS terbaru yang konsepnya tersedia online?

Di sini, dengan "baru", maksud saya sesuatu yang tidak lebih dari ~ 5 tahun.

Beberapa buku TCS oleh Now Publishers dapat ditemukan dalam konsep:

• Dasar-Dasar Kriptografi - Buku Pedoman oleh Oded Goldreich. Ini adalah versi ringkasan dari buku dua jilidnya yang terkenal tentang kriptografi. (Draf versi dua volume dapat ditemukan dalam jawaban Robin .)

• Aliran Data: Algoritma dan Aplikasi oleh S. Muthukrishnan.

• Aspek Matematika Pencampuran Waktu dalam Rantai Markov oleh Montenegro & Tetali.

• Kemandirian Berpasangan dan Derandomisasi oleh Luby & Widgerson.

• Kompleksitas Kasus Rata-rata oleh Bogdanov & Trevisan.

• Sebuah Survei Batas Bawah untuk Kepuasan dan Masalah Terkait oleh Melkebeek.

• Algoritma dan Struktur Data untuk Memori Eksternal oleh Vitter.

• Sistem Bukti Probabilistik: A Primer oleh Goldreich. Sekali lagi, ini adalah versi singkat dari buku Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness .

• Desain Algoritma Online yang Kompetitif melalui Pendekatan Primal-Dual oleh Buchbinder & Naor.

• Algoritma Spektral oleh Kannan & Vempala.

• Tentang Kekuatan Komputasi Kedalaman Kecil oleh Viola.

• Algoritma dan Teknik Analisis dalam Pengujian Properti oleh Ron.

• Sirkuit Aritmatika: Survei Hasil Terbaru dan Pertanyaan Terbuka oleh Amir Shpilka dan Amir Yehudayoff (2010), Yayasan dan Tren® dalam Ilmu Komputer Teoritis: Vol. 5: Tidak. 3-4, hlm. 207-388. http://dx.doi.org/10.1561/0400000039

Selain itu, konsep beberapa buku Springer tentang "Keamanan Informasi dan Kriptografi" dapat ditemukan online:

• Kriptografi dalam Waktu Paralel Konstan oleh Applebaum.

• Sebuah Studi Statistik Zero-Knowledge Proofs oleh Vadhan.

• Kode yang Dapat Didekodekan Secara Lokal dan Skema Pengambilan Informasi Pribadi oleh Yekhanin.

• Concurrent Zero Knowledge oleh Rosen.

Kompleksitas Komputasi Arora dan Barak : Pendekatan Modern , 2010.

Algoritma oleh S. Dasgupta, CH Papadimitriou, dan UV Vazirani

EDIT (16 September '15): Tautan rusak, saya yakin draft tidak lagi tersedia online.

Izinkan saya menambahkan yang berikut:

Combinatorics Analytic , oleh Flajolet dan Sedgewick

Kode dan Automata (Tautan Rusak), oleh Berstel, Perrin dan Reutenauer

Oded Goldreich memiliki beberapa konsep yang tersedia untuk diunduh di halaman web-nya.

• Kompleksitas Komputasi: Perspektif Konseptual (2008)

• P, NP, dan NP-Completeness: The Basics of Complexity Theory (2010)

• The Foundations of Cryptography (2001 dan 2004)

• A Primer on Pseudorandom Generator (2010)

• Pengantar Pengujian Properti (2017)

Teori Grafik Reinhard Diestel (edisi ke-4, 2010), dalam berbagai format elektronik.

Sariel Har-Peled memiliki buku yang akan datang tentang Algoritma Pendekatan Geometrik. Sudah tersedia dalam bentuk draft sebagai catatan kuliah untuk sementara waktu sekarang.

http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/

Expander Graphs dan aplikasinya , oleh Hoory, Linial, dan Wigderson. Ini mendekati wilayah monograf di 123 halaman.

Kompleksitas Fungsi Boolean: Kemajuan dan Batas oleh Stasys Jukna.

(Kata Pengantar) (Daftar Isi)

Draf gratis yang dulu tersedia sebagai unduhan langsung beberapa waktu lalu (jika saya ingat dengan benar), tetapi sekarang tampaknya Anda dapat memperolehnya dengan mengisi formulir di halaman webnya atau mengirim email kepadanya.

Stephen Cook & Phuong Nguyen menerbitkan sebuah buku berjudul Logical Foundations of Proof Complexity pada Maret 2010. Ada draf di situs web Cook: di sini . Sayangnya, saya belum membacanya.

Markov Chains and Mixing Times oleh DA Levin, Y. Peres, EL Wilmer (2008). Akhirnya sebuah buku teks yang membahas topik yang luas dan ada dimana-mana ini.

Ada buku baru yang akan datang tentang Algoritma Spektral oleh Ravi Kannan dan Santosh Vempala yang membahas beberapa perkembangan terbaru. Ini mencakup beberapa aplikasi metode spektral, algoritma untuk memperkirakan parameter spektral dan aproksimasi matriks peringkat rendah.

Karena Suresh Venkat menyebutkan monograf tentang ekspander, saya juga akan menyebutkan monografi terkait berikut tentang topik pseudorandomness . Draf Pseudorandomness oleh Salil Vadhan (220 halaman) sangat layak dibaca. Monograf Parwise Independence and Derandomization oleh Luby dan Wigderson juga bagus!

Buku-buku dalam akses terbuka dari situs Lembaga Penelitian Ilmu Matematika:

• Volume 56, Games of No Chance 3 , diedit oleh Michael H. Albert dan Richard J. Nowakowski, 2009.
• Volume 52, Combinatorial and Computational Geometry , diedit oleh Jacob E. Goodman, János Pach dan Emo Welzl, 2005.
• Volume 44, Teori Angka Algoritma , diedit oleh Joe Buhler dan Peter Stevenhagen, 2008.
• Volume 42, More Games of No Chance , diedit oleh Richard J. Nowakowski, 2002.
• Volume 29, Games of No Chance , diedit oleh Richard Nowakowski, 1996.

Di sini saya hanya mendaftar buku-buku yang menurut saya paling cocok dengan definisi TCS.

NB. Buku bukan konsep dan diterbitkan.

Metode perbedaan , Bernard Chazelle.

Probabilitas pada Pohon dan Jaringan , Russell Lyons dengan Yuval Peres

Keduanya bacaan yang bagus! Anda mungkin ingin mengambil Lyons-Peres sekarang sebelum mereka membuatnya offline.

Buku oleh Bruno Courcelle " Struktur grafik dan logika orde dua monadik, pendekatan teoretis bahasa ".

Teori Permainan Algoritma , oleh Noam Nisan, Tim Roughgarden, Eva Tardos, dan Vijay V. Vazirani (2007).

Aritmatika Komputer Modern oleh RP Brent dan P. Zimmermann.

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: Teknik dan Aplikasi Automata Pohon

"Kompleksitas Deskriptif, Kanonisasi, dan Teori Struktur Grafik Yang Jelas," oleh Martin Grohe. Tanggal pada naskah: 7 Maret 2013. Tersedia di: http://www.automata.rwth-aachen.de/~grohe/pub.en . (Tautan Rusak)

Spektrum Grafik oleh Brouwer dan Haemers . Saya datang ke buku ini melalui Bab 16 (ditulis oleh Spielman) di Combinatorial Scientific Computing .

"Model Komputasi, Menjelajahi Kekuatan Komputasi," oleh John E. Savage. Tersedia di http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .

Teori Automata: Pendekatan Algoritma oleh Javier Esparza

http://www7.in.tum.de/~esparza/automatanotes.html

Ada draf online dari buku baru "Metode Iteratif dalam Optimalisasi Kombinasi" oleh Lap Chi Lau, R. Ravi, dan Mohit Singh:

http://www.cs.mcgill.ca/~mohit/book/book.html

Ini adalah tentang metode pembulatan berulang: teknik baru yang dapat digunakan untuk merancang algoritma aproksimasi untuk banyak masalah.

Catatan atau buku tentang Algoritma Terdistribusi:

• "Kursus tentang Algoritma Terdistribusi Deterministik" oleh Jukka Suomela. Tersedia di http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf
• "Prinsip Komputasi Terdistribusi" oleh Roger Wattenhofer. Tersedia di http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf

"Logika dan Matematika Terpisah untuk Ilmuwan Komputer", oleh James Caldwell. Naskah Tanggal: 22 Agustus 2011. Tersedia di: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

"Struktur Data dan Algoritma, The Basic Toolbox", oleh Kurt Mehlhorn. Naskah Tanggal: Agustus 2008. Tersedia di: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

"Pengantar Teori Grafik dan Jaringan Kompleks", oleh Martin Van Steen. Naskah Tanggal: Januari 2010. Tersedia di: http://www.distributed-systems.net .

"Kategori Teori untuk Ilmu Komputasi," oleh Michael Barr dan Charles Wells. Tersedia di http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

"Filsafat Ilmu Komputer," oleh William J. Rappaport. Naskah Tanggal: 24 Desember 2013. Tersedia di: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

"Teori Grafik Pecahan: Pendekatan Rasional Terhadap Teori Grafik," oleh Edward Scheinerman Dan Daniel Ullman. Tersedia di http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

"Yayasan Ilmu Data" ( pdf ) oleh Hopcroft dan Kannan. Teks itu dibahas oleh Lipton di blog-nya. Sesuai dengan judulnya, penekanan teks tampaknya adalah aplikasi dan masalah yang terkait dengan Big Data dan masalah Pembelajaran. Tampaknya telah tumbuh dari kursus ini .

(Pembaruan 8/2015) Buku ini sekarang memiliki penulis ketiga, Avrim Blum. Tautan pdf telah diperbarui.

PlanetMath mendaftar lebih dari 150 buku yang tersedia online. Daftar ini diperbarui secara berkala (tambahan terbaru adalah 2011-01-09, pada tulisan ini). Buku berhubungan dengan matematika, tetapi beberapa di antaranya juga berguna dalam TCS.

Bayesian Reasoning and Machine Learning , oleh David Barber.

Jaringan, Keramaian, dan Pasar: Beralasan Tentang Dunia yang Sangat Terhubung oleh David Easley dan Jon Kleinberg.

http://www.cs.cornell.edu/home/kleinber/networks-book/