Quais são os livros recentes do TCS cujos rascunhos estão disponíveis online?

Após o post Que livros todos deveriam ler , notei que existem livros recentes cujos rascunhos estão disponíveis online.

Por exemplo, a entrada Algoritmos de aproximação do post acima cita um livro de 2011 (ainda a ser publicado) intitulado O design de algoritmos de aproximação .

Eu acho que conhecer trabalhos recentes é realmente útil para quem quiser conhecer as tendências da TCS. Quando os rascunhos estão disponíveis, é possível verificar os livros antes de comprá-los.

Assim,

Quais são os livros recentes do TCS cujos rascunhos estão disponíveis online?

Aqui, por "recente", quero dizer algo que não tem mais que ~ 5 anos.

Vários livros do Now Publishers do TCS podem ser encontrados em rascunhos:

• Fundamentos de criptografia - Uma cartilha de Oded Goldreich. Esta é uma versão resumida de seu famoso livro de dois volumes sobre criptografia. (O rascunho da versão em dois volumes pode ser encontrado na resposta de Robin .)

• Fluxos de Dados: Algoritmos e Aplicações por S. Muthukrishnan.

• Aspectos matemáticos dos tempos de mistura nas cadeias de Markov por Montenegro e Tetali.

• Independência Pairwise e Derandomization por Luby & Widgerson.

• Complexidade de casos médios de Bogdanov & Trevisan.

• Uma pesquisa sobre limites mais baixos de satisfação e problemas relacionados por Melkebeek.

• Algoritmos e estruturas de dados para memória externa por Vitter.

• Sistemas probabilísticos de prova: uma cartilha de Goldreich. Novamente, esta é uma versão resumida do livro de Goldreich, parte Modern Cryptography, Probabilistic Proofs and Pseudorandomness .

• O Projeto de Algoritmos Online Competitivos através de uma Abordagem Primal-Dual da Buchbinder & Naor.

• Algoritmos espectrais de Kannan e Vempala.

• Sobre o poder da computação em pequena profundidade da Viola.

• Técnicas Algorítmicas e de Análise em Teste de Propriedades por Ron.

• Circuitos Aritméticos: Uma Pesquisa de Resultados Recentes e Perguntas Abertas de Amir Shpilka e Amir Yehudayoff (2010), Foundations and Trends® em Teoria da Computação: vol. 5: No. 3-4, pp 207-388. http://dx.doi.org/10.1561/0400000039

Além disso, rascunhos de vários livros da Springer sobre "Segurança e criptografia da informação" podem ser encontrados on-line:

• Criptografia em Tempo Paralelo Constante por Applebaum.

• Um estudo de provas estatísticas de zero conhecimento por Vadhan.

• Códigos localmente decodíveis e esquemas de recuperação de informações particulares da Yekhanin.

• Conhecimento zero simultâneo de Rosen.

Complexidade Computacional de Arora e Barak : Uma Abordagem Moderna , 2010.

Algoritmos de S. Dasgupta, CH Papadimitriou e UV Vazirani

EDIT (16 de setembro de 15): o link está quebrado, acredito que o rascunho não está mais disponível online.

Deixe-me adicionar o seguinte:

Combinatória analítica , de Flajolet e Sedgewick

Codes and Automata (Link Broken), por Berstel, Perrin e Reutenauer

Oded Goldreich tem vários rascunhos disponíveis para download em sua página da web.

• Complexidade Computacional: Uma Perspectiva Conceitual (2008)

• P, NP e NP-Completeness: Os princípios da teoria da complexidade (2010)

• Os Fundamentos da Criptografia (2001 e 2004)

• Uma cartilha sobre geradores pseudo-aleatórios (2010)

• Introdução aos testes de propriedade (2017)

Teoria dos Gráficos de Reinhard Diestel (4ª edição, 2010), em uma variedade de formatos eletrônicos.

Sariel Har-Peled tem um próximo livro sobre algoritmos de aproximação geométrica. Já está disponível em forma de rascunho como notas de aula.

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

Expander Graphs e suas aplicações , por Hoory, Linial e Wigderson. Isso está chegando ao território da monografia em 123 páginas.

Complexidade da função booleana: avanços e fronteiras por Stasys Jukna.

(Prefácio) (Sumário)

Um rascunho gratuito costumava estar disponível para download direto há um tempo atrás (se bem me lembro), mas agora parece que você pode obtê-lo preenchendo um formulário na página dele ou enviando um e-mail.

Stephen Cook e Phuong Nguyen publicaram um livro chamado Logical Foundations of Proof Complexity em março de 2010. Há um rascunho no site de Cook: aqui . Infelizmente, eu não li.

Markov Chains and Mixing Times de DA Levin, Y. Peres, EL Wilmer (2008). Finalmente, um livro de texto abordando esse tópico amplo e onipresente.

Há um novo livro sobre os algoritmos espectrais de Ravi Kannan e Santosh Vempala, cobrindo vários desenvolvimentos mais recentes. Abrange várias aplicações de métodos espectrais, algoritmos para estimativa de parâmetros espectrais e aproximação de matrizes de baixa classificação.

Como Suresh Venkat mencionou a monografia sobre expansores, também mencionarei as seguintes monografias relacionadas ao tópico pseudo-aleatoriedade . Vale a pena ler o rascunho de Pseudorandomness de Salil Vadhan (220 páginas). A monografia Parwise Independence and Derandomization de Luby e Wigderson também é legal!

Os livros em acesso aberto no site do Instituto de Pesquisa em Ciências Matemáticas:

• Volume 56, Games of No Chance 3 , editado por Michael H. Albert e Richard J. Nowakowski, 2009.
• Volume 52, Geometria Combinatória e Computacional , editado por Jacob E. Goodman, János Pach e Emo Welzl, 2005.
• Volume 44, Algorithmic Number Theory , editado por Joe Buhler e Peter Stevenhagen, 2008.
• Volume 42, Mais jogos sem chance , editado por Richard J. Nowakowski, 2002.
• Volume 29, Games of No Chance , editado por Richard Nowakowski, 1996.

Aqui, listei apenas os livros que, para mim, se encaixam melhor na definição de TCS.

NB Livros não são rascunhos e foram publicados.

O método da discrepância , Bernard Chazelle.

Probabilidade em árvores e redes , Russell Lyons com Yuval Peres

Ambos são ótimas leituras! Convém pegar o Lyons-Peres agora antes de colocá-lo offline.

Livro de Bruno Courcelle " Estrutura gráfica e lógica monádica de segunda ordem, uma abordagem teórica da linguagem ".

Algorithmic Game Theory , de Noam Nisan, Tim Roughgarden, Eva Tardos e Vijay V. Vazirani (2007).

Aritmética computacional moderna por RP Brent e P. Zimmermann.

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison e Marc Tommasi: Técnicas e Aplicações de Autômatos em Árvore

"Complexidade descritiva, canonização e teoria das estruturas de gráficos definíveis", de Martin Grohe. Data do manuscrito: 7 de março de 2013. Disponível em: http://www.automata.rwth-aachen.de/~grohe/pub.en . (Link quebrado)

Espectros de gráficos de Brouwer e Haemers . Cheguei a este livro por meio do capítulo 16 (escrito por Spielman) em Combinatorial Scientific Computing .

"Modelos de computação, explorando o poder da computação", de John E. Savage. Disponível em http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .

Teoria dos Autômatos: Uma Abordagem Algorítmica por Javier Esparza

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

Há um rascunho on-line do novo livro "Métodos iterativos na otimização combinatória", de Lap Chi Lau, R. Ravi e Mohit Singh:

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

Trata-se do método de arredondamento iterativo: uma nova técnica que pode ser usada para projetar algoritmos de aproximação para muitos problemas.

Notas ou livros sobre algoritmos distribuídos:

• "Um curso sobre algoritmos distribuídos determinísticos", de Jukka Suomela. Disponível em http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf
• "Princípios de computação distribuída", de Roger Wattenhofer. Disponível em http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf

"Matemática lógica e discreta para cientistas da computação", de James Caldwell. Data do manuscrito: 22 de agosto de 2011. Disponível em: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

"Estruturas de dados e algoritmos, The Basic Toolbox", de Kurt Mehlhorn. Data do manuscrito: agosto de 2008. Disponível em: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

"Uma introdução à teoria dos grafos e redes complexas", de Martin Van Steen. Data do manuscrito: janeiro de 2010. Disponível em: http://www.distributed-systems.net .

"Teoria da categoria para a ciência da computação", de Michael Barr e Charles Wells. Disponível em http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

"Filosofia da Ciência da Computação", de William J. Rappaport. Data do manuscrito: 24 de dezembro de 2013. Disponível em: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

"Teoria dos grafos fracionários: uma abordagem racional da teoria dos grafos", de Edward Scheinerman e Daniel Ullman. Disponível em http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

"Foundations of Data Science" ( pdf ) por Hopcroft e Kannan. O texto foi discutido por Lipton em seu blog. Como o título indica, a ênfase do texto parece ser aplicações e questões relacionadas a problemas de Big Data e Aprendizado. Parece ter crescido fora deste curso .

(Atualização 8/2015) O livro agora tem um terceiro autor, Avrim Blum. O link do pdf foi atualizado.

O PlanetMath lista mais de 150 livros disponíveis online. A lista é atualizada regularmente (a adição mais recente foi 09/01/2011, até o momento em que este documento foi escrito). Os livros são relacionados à matemática, mas alguns também são úteis no TCS.

Raciocínio Bayesiano e Aprendizado de Máquina , de David Barber.

Redes, multidões e mercados: raciocínio sobre um mundo altamente conectado por David Easley e Jon Kleinberg.

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