Jakie są najnowsze książki TCS, których wersje robocze są dostępne online?

Idąc za postem Co książki powinny przeczytać wszystkie , zauważyłem, że są ostatnie książki, których wersje robocze są dostępne online.

Na przykład pozycja Algorytmy aproksymacji powyższego wpisu cytuje książkę z 2011 r. (Jeszcze do opublikowania) zatytułowaną Projektowanie algorytmów aproksymacyjnych .

Myślę, że znajomość najnowszych prac jest naprawdę przydatna dla każdego, kto chce poznać trendy TCS. Kiedy są dostępne wersje robocze, można sprawdzić książki przed ich faktycznym zakupem.

Więc,

Jakie są najnowsze książki TCS, których wersje robocze są dostępne online?

Tutaj przez „ostatnie” rozumiem coś, co nie jest starsze niż ~ 5 lat.

Kilka książek TCS autorstwa Now Publishers można znaleźć w szkicach:

• Podstawy kryptografii - elementarz Odeda Goldreicha. To jest skrócona wersja jego słynnej dwumotomowej książki o kryptografii. (Szkic wersji dwóch tomów można znaleźć w odpowiedzi Robina .)

• Strumienie danych: algorytmy i aplikacje S. Muthukrishnan.

• Matematyczne aspekty czasów mieszania w łańcuchach Markowa Czarnogóry i Tetali.

• Niezależność parowa i derandomizacja przez Luby & Widgerson.

• Średnia złożoność przypadków według Bogdanova i Trevisana.

• Badanie dolnych granic satysfakcji i powiązanych problemów Melkebeek.

• Algorytmy i struktury danych dla pamięci zewnętrznej według Vittera.

• Probabilistic Proof Systems: A Primer firmy Goldreich. Ponownie, jest to podsumowana wersja części książki Goldreicha Modern Cryptography, Probabilistic Proofs and Pseudorandomness .

• Projektowanie konkurencyjnych algorytmów online za pomocą podejścia pierwotnego podwójnego autorstwa Buchbindera i Naora.

• Algorytmy spektralne Kannana i Vempali.

• O sile obliczeń o małej głębokości autorstwa Violi.

• Techniki algorytmiczne i analityczne w testowaniu właściwości Rona.

• Obwody arytmetyczne: badanie ostatnich wyników i otwartych pytań Amira Shpilki i Amira Yehudayoffa (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: nr 3–4, s. 207-388. http://dx.doi.org/10.1561/0400000039

Ponadto szkice kilku książek Springera na temat „Bezpieczeństwo informacji i kryptografia” można znaleźć w Internecie:

• Kryptografia w stałym czasie równoległym Applebaum.

• Badanie statystycznych dowodów zerowej wiedzy autorstwa Vadhana.

• Lokalnie dekodowane kody i schematy wyszukiwania prywatnych informacji przez Yekhanin.

• Jednoczesna zerowa wiedza autorstwa Rosen.

Złożoność obliczeniowa Arory i Baraka : nowoczesne podejście , 2010.

Algorytmy S. Dasgupta, CH Papadimitriou i UV Vazirani

EDYCJA (16 września 15): link jest zepsuty, uważam, że projekt nie jest już dostępny online.

Pozwól mi dodać następujące:

Analytic Combinatorics , Flajolet i Sedgewick

Kody i automaty (Link Broken), autorstwa Berstel, Perrin i Reutenauer

Oded Goldreich ma kilka szkiców do pobrania na swojej stronie internetowej.

• Złożoność obliczeniowa: perspektywa koncepcyjna (2008)

• P, NP i NP-Kompletność: podstawy teorii złożoności (2010)

• Podstawy kryptografii (2001 i 2004)

• Elementarz na pseudolosowych generatorach (2010)

• Wprowadzenie do testowania właściwości (2017)

Teoria grafów Reinharda Diestela (4. edycja, 2010), w różnych formatach elektronicznych.

Sariel Har-Peled ma nadchodzącą książkę na temat algorytmów aproksymacji geometrycznej. Od pewnego czasu jest dostępny w wersji roboczej jako notatki do wykładu.

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

Grafy ekspanderów i ich zastosowania , Hoory, Linial i Wigderson. Zbliża się to do terytorium monografii na 123 stronach.

Złożoność funkcji logicznej: postępy i granice autorstwa Stasysa Jukny.

(Przedmowa) (spis treści)

Darmowy projekt był kiedyś dostępny do bezpośredniego pobrania (jeśli dobrze pamiętam), ale teraz wydaje się, że możesz go uzyskać, wypełniając formularz na jego stronie internetowej lub wysyłając mu wiadomość e-mail.

Stephen Cook i Phuong Nguyen opublikowali książkę pod tytułem Logiczne podstawy dowodu złożoności w marcu 2010 roku. Na stronie internetowej Cooka jest szkic: tutaj . Niestety nie przeczytałem tego.

Markov Chains and Mixing Times autorstwa DA Levina, Y. Peresa, EL Wilmera (2008). Wreszcie książka o tym szerokim i wszechobecnym temacie.

Pojawiła się nowa książka Ravi Kannana i Santosha Vempali na temat algorytmów spektralnych, zawierająca kilka najnowszych osiągnięć. Obejmuje kilka zastosowań metod spektralnych, algorytmów do szacowania parametrów widmowych i aproksymacji macierzy niskiej rangi.

Ponieważ Suresh Venkat wspomniał o monografii ekspanderów, wspomnę również o następujących powiązanych monografiach na temat pseudolosowości . Szkic Pseudorandomness autorstwa Salila Vadhana (220 stron) jest bardzo wart przeczytania. Monografia Parwise Independence and Derandomization autorstwa Luby i Wigderson jest również miła!

Książki w otwartym dostępie ze strony Instytutu Nauk Matematycznych:

• Tom 56, Games of No Chance 3 , pod redakcją Michaela H. Alberta i Richarda J. Nowakowskiego, 2009.
• Tom 52, Geometria kombinatoryczna i obliczeniowa , pod redakcją Jacob E. Goodman, János Pach i Emo Welzl, 2005.
• Tom 44, Algorytmiczna teoria liczb , pod redakcją Joe Buhlera i Petera Stevenhagen, 2008.
• Tom 42, Więcej gier bez szans , pod redakcją Richarda J. Nowakowskiego, 2002.
• Tom 29, Gry bez szans , pod redakcją Richarda Nowakowskiego, 1996.

Tutaj wymieniłem tylko te książki, które według mnie najlepiej pasują do definicji TCS.

NB. Książki nie są szkicami i zostały opublikowane.

Metoda rozbieżności , Bernard Chazelle.

Prawdopodobieństwo na drzewach i sieciach , Russell Lyons i Yuval Peres

Oba są świetne do czytania! Być może zechcesz teraz wziąć Lyons-Peres, zanim przejdą w tryb offline.

Książka Bruno Courcelle'a „ Struktura wykresu i monadyczna logika drugiego rzędu, podejście teoretyczne ”.

Algorytmiczna teoria gier , autor: Noam Nisan, Tim Roughgarden, Eva Tardos i Vijay V. Vazirani (2007).

Modern Computer Arithmetic autorstwa RP Brenta i P. Zimmermanna.

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: Tree Automata Techniques and Applications

„Złożoność opisowa, kanonizacja i teoria struktury grafu definiowalnego” - Martin Grohe. Data w rękopisie: 7 marca 2013 r. Dostępny pod adresem : http://www.automata.rwth-aachen.de/~grohe/pub.en . (Link Broken)

Widma wykresów przez Brouwera i Haemers . Do tej książki doszedłem na podstawie rozdziału 16 (napisanego przez Spielmana) w Combinatorial Scientific Computing .

„Modele obliczeń, odkrywanie mocy obliczeń”, John E. Savage. Dostępne pod adresem http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .

Teoria automatów: podejście algorytmiczne Javiera Esparza

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

Istnieje szkic online nowej książki „Iterative Methods in Combinatorial Optimization” autorstwa Lap Chi Lau, R. Raviego i Mohita Singha:

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

Chodzi o iteracyjną metodę zaokrąglania: nową technikę, której można użyć do zaprojektowania algorytmów aproksymacyjnych dla wielu problemów.

Uwagi lub książki na temat algorytmów rozproszonych:

• „Kurs o deterministycznych algorytmach rozproszonych” Jukki Suomeli. Dostępne na http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf
• „Zasady przetwarzania rozproszonego” Rogera Wattenhofera. Dostępny na stronie http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf

„Logika i dyskretna matematyka dla informatyków” Jamesa Caldwella. Data rękopisu: 22 sierpnia 2011 r. Dostępny pod adresem : http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

„Struktury i algorytmy danych, podstawowy zestaw narzędzi”, Kurt Mehlhorn. Data rękopisu: sierpień 2008 r. Dostępny pod adresem : http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

„Wprowadzenie do teorii grafów i złożonych sieci”, Martin Van Steen. Data rękopisu: styczeń 2010 r. Dostępny na stronie : http://www.distribution-systems.net .

„Kategoria teorii dla informatyki” Michaela Barra i Charlesa Wellsa. Dostępne na stronie http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

„Philosophy of Computer Science” Williama J. Rappaporta. Data rękopisu: 24 grudnia 2013 r. Dostępny pod adresem : http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

„Fractional Graph Theory: Rational Approach To Theory of Graphs”, Edward Scheinerman i Daniel Ullman. Dostępne na stronie http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

„Podstawy nauki o danych” ( pdf ) Hopcroft i Kannan. Tekst omówił Lipton na swoim blogu. Jak sugeruje tytuł, nacisk kładziony jest na aplikacje i problemy związane z Big Data i problemami z uczeniem się. Wydaje się, że wyrósł z tego kursu .

(Aktualizacja 8/2015) Książka ma teraz trzeciego autora, Avrim Blum. Link pdf został zaktualizowany.

PlanetMath wymienia ponad 150 książek dostępnych online. Lista jest regularnie aktualizowana (najnowszym dodatkiem jest 2011-01-09, począwszy od tego pisania). Książki są związane z matematyką, ale niektóre z nich są również przydatne w TCS.

Bayesian Reasoning and Machine Learning , David Barber.

Sieci, tłumy i rynki: rozumowanie o wysoce połączonym świecie autorstwa Davida Easleya i Jona Kleinberga.

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