¿Cuáles son los libros recientes de TCS cuyos borradores están disponibles en línea?

99

Después de la publicación Qué libros deberían leer todos , noté que hay libros recientes cuyos borradores están disponibles en línea.

Por ejemplo, la entrada de Algoritmos de aproximación de la publicación anterior cita un libro de 2011 (aún por publicar) titulado El diseño de algoritmos de aproximación .

Creo que conocer trabajos recientes es realmente útil para quien quiera probar las tendencias de TCS. Cuando hay borradores disponibles, uno puede consultar los libros antes de comprarlos.

Entonces,

¿Cuáles son los libros recientes de TCS cuyos borradores están disponibles en línea?

Aquí, por "reciente", me refiero a algo que no tiene más de ~ 5 años.

Rahab
fuente
2
Lo he marcado para convertirme en CW.
Rahab
2
Sería bueno si las respuestas se convierten en CW también para que podamos votarlas.
Kaveh
las respuestas se convierten en CW por defecto si la pregunta es CW.
Suresh Venkat
3
@Suresh: Pero ya tenemos respuestas que no son de CW y también deberían convertirse en CW.
Jukka Suomela
@Suresh y @Jukka, ¿cómo puedo personalizar mi respuesta?
Alessandro Cosentino

Respuestas:

43

Se pueden encontrar varios libros de TCS de Now Publishers en borradores:


Además, se pueden encontrar borradores de varios libros de Springer sobre "Seguridad de la información y criptografía" en línea:

MS Dousti
fuente
38

Complejidad computacional de Arora y Barak : un enfoque moderno , 2010.

M. Alaggan
fuente
29
Una advertencia. el borrador es realmente eso: un borrador. Hay numerosos errores en el borrador que se corrigieron en la versión impresa (lo sé porque dirigí un grupo de lectura de verano usando el borrador y tuve que corregirlo constantemente del libro)
Suresh Venkat
44
Vale la pena comprar el libro. No es caro en absoluto por su valor y tamaño.
Dai Le
37

Algoritmos de S. Dasgupta, CH Papadimitriou y UV Vazirani

EDITAR (16 de septiembre de 2015): el enlace está roto, creo que el borrador ya no está disponible en línea.

Alessandro Cosentino
fuente
El enlace está roto a partir del 10/12/2013. ¿Quizás el acceso en línea ya no está disponible?
Logan Mayfield
1
@LoganMayfield es extraño, porque aún puedes acceder a los capítulos individuales aquí: cs.berkeley.edu/~vazirani/algorithms
Alessandro Cosentino
1
Aquí hay un enlace para el libro cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
drzbir
27

Sariel Har-Peled tiene un próximo libro sobre Algoritmos de aproximación geométrica. Ha estado disponible en forma de borrador como notas de clase desde hace un tiempo.

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

Chandra Chekuri
fuente
arggh. ¿Cómo demonios olvidé ese?
Suresh Venkat
1
@Suresh: (Es broma) Un momento importante, quizás;)
MS Dousti
arggh. más como un momento de falta de café :)
Suresh Venkat
55
Y ya no está disponible en línea: la fecha de publicación se está acercando y le prometí al editor (AMS) que no la publicará en línea. Lo siento ...
Sariel Har-Peled
25

Complejidad de la función booleana: avances y fronteras por Stasys Jukna.

(Prefacio) (Tabla de contenido)

Un borrador gratuito solía estar disponible como descarga directa hace un tiempo (si no recuerdo mal), pero ahora parece que puede obtenerlo completando un formulario en su página web o enviándole un correo electrónico.

Robin Kothari
fuente
1
Sobre el tema de las funciones booleanas y el análisis de Fourier: Análisis de funciones booleanas , por Ryan O'Donnell (2014): la versión en pdf está disponible aquí .
Clemente C.
24

Stephen Cook y Phuong Nguyen publicaron un libro llamado Fundamentos lógicos de la complejidad de la prueba en marzo de 2010. Hay un borrador en el sitio web de Cook: aquí . Lamentablemente, no lo he leído.

Michael Blondin
fuente
3
El Capítulo 2 ya es una introducción muy elegante a la lógica proposicional y la lógica de primer orden, con herramientas importantes como Completitud, Compacidad, Löwenheim – Skolem y el Teorema de Hebrand.
Dai Le
3
He leído muchas partes del libro y lo recomiendo encarecidamente a las personas interesadas en la complejidad y la lógica. Para las personas que trabajan en pruebas de complejidad, creo que posiblemente sea una necesidad. No trata los límites inferiores de la complejidad de la prueba, que es el tema principal del tema, pero brinda el contexto lógico esencial de la complejidad de la prueba. Es especialmente adecuado para principiantes y para el autoaprendizaje. Literalmente, no se asume ningún conocimiento previo, todo se explica desde cero y se proporcionan detalles completos para todo. (Además, el borrador es casi el mismo que el libro.)
Iddo Tzameret
22

Cadenas de Markov y tiempos de mezcla por DA Levin, Y. Peres, EL Wilmer (2008). Finalmente un libro de texto que cubre este tema amplio y omnipresente.

Martin Schwarz
fuente
1
ahora ese es un buen libro.
Suresh Venkat
21

Hay un nuevo libro próximo sobre Algoritmos espectrales de Ravi Kannan y Santosh Vempala que cubre varios desarrollos más recientes. Cubre varias aplicaciones de métodos espectrales, algoritmos para estimar parámetros espectrales y aproximación de bajo rango de matrices.

Shiva Kintali
fuente
20

Como Suresh Venkat mencionó la monografía sobre expansores, también mencionaré las siguientes monografías relacionadas sobre el tema de la pseudoaleatoriedad . El proyecto de pseudoaleatoriedad por Salil Vadhan (220 páginas) es muy vale la pena leer. La monografía Parwise Independence and Derandomization de Luby y Wigderson también es agradable.

Dai Le
fuente
18

Los libros en acceso abierto desde el sitio del Instituto de Investigación de Ciencias Matemáticas:

Aquí he enumerado solo aquellos libros que para mí encajan mejor en la definición de TCS.

NÓTESE BIEN. Los libros no son borradores y fueron publicados.

Oleksandr Bondarenko
fuente
2
Wow, excelente fuente!
Dai Le
10

Hay un borrador en línea del nuevo libro "Métodos iterativos en optimización combinatoria" de Lap Chi Lau, R. Ravi y Mohit Singh:

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

Se trata del método de redondeo iterativo: una nueva técnica que se puede utilizar para diseñar algoritmos de aproximación para muchos problemas.

Bart
fuente
10

"Matemática lógica y discreta para informáticos", por James Caldwell. Fecha del manuscrito: 22 de agosto de 2011. Disponible en: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

"Estructuras de datos y algoritmos, la caja de herramientas básica", por Kurt Mehlhorn. Fecha del manuscrito: agosto de 2008. Disponible en: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

"Una introducción a la teoría de grafos y redes complejas", por Martin Van Steen. Fecha del manuscrito: enero de 2010. Disponible en: http://www.distributed-systems.net .

"Teoría de la categoría para la ciencia de la computación", de Michael Barr y Charles Wells. Disponible en http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

"Filosofía de la informática", por William J. Rappaport. Fecha del manuscrito: 24 de diciembre de 2013. Disponible en: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

"Teoría de gráficos fraccionales: un enfoque racional de la teoría de gráficos", por Edward Scheinerman y Daniel Ullman. Disponible en http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

revs lgidwani
fuente
10

"Fundamentos de la ciencia de datos" ( pdf ) por Hopcroft y Kannan. El texto fue discutido por Lipton en su blog. Como el título lo indica, el énfasis del texto parece ser aplicaciones y problemas relacionados con Big Data y problemas de aprendizaje. Parece haber surgido de este curso .

(Actualización 8/2015) El libro ahora tiene un tercer autor, Avrim Blum. El enlace pdf ha sido actualizado.

Logan Mayfield
fuente
1
versión más reciente: cs.cornell.edu/jeh/book112013.pdf
domotorp
y creo que el título es Fundamentos de la ciencia de datos.
domotorp
Se actualizó el enlace a la versión de abril de 2014 que se encuentra en el sitio web de Hopcroft.
Logan Mayfield
8

PlanetMath enumera más de 150 libros que están disponibles en línea. La lista se actualiza regularmente (la adición más reciente es 2011-01-09, a partir de este escrito). Los libros están relacionados con las matemáticas, pero algunos de ellos también son útiles en TCS.

MS Dousti
fuente
¿enlace por favor? No pude encontrar esa lista en PlanetMath ...
Joshua Grochow
@JoshuaGrochow: Desafortunadamente, el enlace anterior que proporcioné anteriormente ya no funciona. Lo reemplazaré tan pronto como encuentre el nuevo enlace.
MS Dousti