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

99

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.

Rahab
źródło
2
Oflagowałem go jako CW.
Rahab,
2
Byłoby miło, gdyby odpowiedzi zmieniły się również w CW, abyśmy mogli je głosować.
Kaveh,
odpowiedzi stają się domyślnie CW, jeśli pytanie brzmi CW.
Suresh Venkat,
3
@Suresh: Ale mamy już odpowiedzi spoza CW i należy je również zamienić na CW.
Jukka Suomela,
@Suresh i @Jukka, jak mogę CWize moją odpowiedź?
Alessandro Cosentino,

Odpowiedzi:

43

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


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

MS Dousti
źródło
38

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

M. Alaggan
źródło
29
Ostrzeżenie. projekt jest po prostu taki: projekt. W szkicu jest wiele błędów, które zostały naprawione w wersji drukowanej (wiem o tym, ponieważ prowadziłem letnią grupę czytelniczą przy użyciu szkicu i musiałem ciągle go poprawiać z książki)
Suresh Venkat,
4
Książkę naprawdę warto kupić. Nie jest wcale drogi ze względu na swoją wartość i rozmiar.
Dai Le
37

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.

Alessandro Cosentino
źródło
Link jest zerwany na dzień 12.10.2013. Być może dostęp online nie jest już dostępny?
Logan Mayfield,
1
@LoganMayfield to dziwne, ponieważ nadal możesz uzyskać dostęp do pojedynczych rozdziałów tutaj: cs.berkeley.edu/~vazirani/algorithms
Alessandro Cosentino
1
Oto link do książki cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
drzbir
27

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/

Chandra Chekuri
źródło
arggh. jak, do licha, zapomniałem o tym!
Suresh Venkat,
1
@Suresh: (tylko żartuję) Być może starszy moment;)
MS Dousti
arggh. bardziej jak chwila braku kawy :)
Suresh Venkat
5
I nie jest już dostępny online - data publikacji zbliża się, a ja obiecałem wydawcy (AMS), że nie opublikuję go online. Przepraszam ...
Sariel Har-Peled,
25

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.

Robin Kothari
źródło
1
Na temat funkcji boolowskich i analizy Fouriera: Analiza funkcji boolowskich , autor: Ryan O'Donnell (2014): wersja pdf jest dostępna tutaj .
Klemens C.
24

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.

Michael Blondin
źródło
3
Sam rozdział 2 jest już bardzo eleganckim wprowadzeniem do logiki zdań i logiki pierwszego rzędu, z ważnymi narzędziami, takimi jak kompletność, zwartość, Löwenheim – Skolem i twierdzenie Hebranda.
Dai Le
3
Przeczytałem wiele części książki i bardzo polecam ją osobom zainteresowanym złożonością i logiką. Dla osób pracujących w złożonym dowodzie myślę, że być może jest to konieczne. Nie zajmuje się dolnymi granicami złożoności dowodu, co jest głównym problemem tego tematu, ale daje podstawowy logiczny kontekst złożoności dowodu. Jest szczególnie odpowiedni dla początkujących i do samodzielnej nauki. Dosłownie, nie zakłada się wcześniejszej wiedzy, wszystko jest wyjaśnione od zera i podano wszystkie szczegóły. (Również szkic jest prawie taki sam jak w książce.)
Iddo Tzameret
22

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

Martin Schwarz
źródło
1
to fajna książka.
Suresh Venkat,
21

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.

Shiva Kintali
źródło
20

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!

Dai Le
źródło
18

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

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.

Oleksandr Bondarenko
źródło
2
Wow, doskonałe źródło!
Dai Le
10

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.

Bart
źródło
10

„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 .

lgidwani
źródło
10

„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.

Logan Mayfield
źródło
1
nowsza wersja: cs.cornell.edu/jeh/book112013.pdf
domotorp
i myślę, że tytuł to Foundations of Data Science.
domotorp
Zaktualizowano link do wersji z kwietnia 2014 r. Znalezionej na stronie internetowej Hopcroft.
Logan Mayfield
8

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.

MS Dousti
źródło
link proszę? Nie mogłem znaleźć tej listy na PlanetMath ...
Joshua Grochow
@JoshuaGrochow: Niestety stary link, który podałem powyżej, już nie działa. Zastąpię go, jak tylko znajdę nowy link.
MS Dousti