Каковы последние книги TCS, проекты которых доступны онлайн?

После публикации « Что должны читать все книги» я заметил, что есть недавние книги, черновики которых доступны в Интернете.

Например, в статье « Алгоритмы аппроксимации» вышеприведенного поста цитируется книга 2011 года (еще не опубликованная) под названием «Разработка алгоритмов аппроксимации» .

Я думаю, что знание последних работ действительно полезно для тех, кто хочет получить представление о тенденциях TCS. Когда черновики доступны, можно проверить книги, прежде чем покупать их.

Так,

Каковы последние книги TCS, проекты которых доступны онлайн?

Здесь под «недавним» я подразумеваю то, что не старше ~ 5 лет.

Несколько книг TCS от Now Publishers можно найти в черновиках:

• Основы криптографии - учебник Одеда Голдрайха. Это краткая версия его знаменитой двухтомной книги по криптографии. (Черновик двухтомной версии можно найти в ответе Робина .)

• Потоки данных: алгоритмы и приложения С. Мутукришнана.

• Математические аспекты смешивания времен в цепях Маркова Черногории и Тетали.

• Парная независимость и дерандомизация от Luby & Widgerson.

• Сложность среднего случая Богданова и Тревизана.

• Обзор нижних границ удовлетворенности и связанных с этим проблем Melkebeek.

• Алгоритмы и структуры данных для внешней памяти по Vitter.

• Вероятностные системы доказательств: учебник по Голдрайху. Опять же, это обобщенная версия книги Голдрайха « Современная криптография, вероятностные доказательства и псевдослучайность» .

• Разработка конкурентных онлайн-алгоритмов по принципу Primal-Dual по Buchbinder & Naor.

• Спектральные алгоритмы Каннана и Вемпалы.

• О мощи малых глубин вычислений альта.

• Алгоритмические и аналитические методы в тестировании свойств по Рон.

• Арифметические схемы: обзор последних результатов и открытых вопросов Амир Шпилка и Амир Yehudayoff (2010), Основы и тенденции ® в теоретической информатике: Vol. 5: № 3–4, с. 207–388. http://dx.doi.org/10.1561/0400000039

Кроме того, в Интернете можно найти проекты нескольких книг Springer на тему «Информационная безопасность и криптография» :

• Криптография в постоянном параллельном времени по Эпплбауму.

• Исследование статистических доказательств нулевого знания Вадханом.

• Декодируемые локально коды и схемы поиска частной информации Еханина.

• Нулевое Знание от Розена.

Вычислительная сложность ароры и барака: современный подход , 2010.

Алгоритмы С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани

РЕДАКТИРОВАТЬ (16 сентября '15): ссылка не работает, я думаю, что черновик больше не доступен в Интернете.

Позвольте мне добавить следующее:

Аналитическая комбинаторика , Флаолет и Седжвик

Коды и автоматы (ссылка сломана), Берстель, Перрин и Рейтенауэр

У Одеда Голдрайха есть несколько черновиков, доступных для скачивания на его веб-странице.

• Вычислительная сложность: концептуальная перспектива (2008)

• P, NP и NP-Полнота: основы теории сложности (2010)

• Основы криптографии (2001 и 2004)

• Учебник по псевдослучайным генераторам (2010)

• Введение в тестирование недвижимости (2017)

Теория графов Рейнхарда Дистеля (4-е издание, 2010 г.) в различных электронных форматах.

У Сариэля Хар-Пеледа есть новая книга по алгоритмам геометрической аппроксимации. Некоторое время он был доступен в виде черновика в виде конспекта лекции.

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

Графы расширителей и их приложения , Hoory, Linial и Wigderson. Это на грани монографии на 123 страницах.

Сложность булевой функции: достижения и границы . Стасис Юкна.

(Предисловие) (Содержание)

Раньше бесплатный черновик был доступен для прямой загрузки (если я правильно помню), но теперь, кажется, вы можете получить его, заполнив форму на его веб-странице или отправив ему электронное письмо.

Стивен Кук и Фуонг Нгуен опубликовали книгу под названием « Логические основы сложности доказательств» в марте 2010 года. На сайте Кука есть черновик: здесь . К сожалению, я не читал это.

Марковские цепи и времена смешивания Д. А. Левин, Ю. Перес, Е. Л. Уилмер (2008). Наконец учебник, охватывающий эту широкую и вездесущую тему.

Новая книга о спектральных алгоритмах Рави Каннана и Сантоша Вемпалы, посвященная нескольким последним разработкам. Он охватывает несколько применений спектральных методов, алгоритмов оценки спектральных параметров и аппроксимации матриц низкого ранга.

Поскольку Суреш Венкат упомянул монографию о расширителях, я также упомяну следующие смежные монографии на тему псевдослучайности . Черновик псевдослучайности Салила Вадхана (220 страниц) очень стоит прочитать. Монография Parwise Independence и Derandomization от Люби и Вигдерсона также хороша!

Книги в открытом доступе с сайта НИИ математических наук:

• Том 56, Игры без шансов 3 , под редакцией Майкла Х. Альберта и Ричарда Дж. Новаковски, 2009.
• Том 52, Комбинаторная и вычислительная геометрия , под редакцией Якоба Э. Гудмана, Яноша Паха и Эмо Вельцля, 2005.
• Том 44, Алгоритмическая теория чисел , под редакцией Джо Бюлера и Питера Стивенхагена, 2008.
• Том 42, Больше игр без шансов , под редакцией Ричарда Дж. Новаковски, 2002.
• Том 29, Игры без шансов , под редакцией Ричарда Новаковски, 1996.

Здесь я перечислил только те книги, которые мне лучше всего подходят под определение TCS.

NB. Книги не являются черновиками и были опубликованы.

Метод расхождения Бернар Шазель.

Вероятность на деревьях и сетях , Рассел Лайонс и Юваль Перес

Оба отлично читают! Возможно, вы захотите захватить Lyons-Peres сейчас, прежде чем они отключат его.

Книга Бруно Курселя " Структура графов и монадическая логика второго порядка, теоретико-языковой подход ".

Алгоритмическая теория игр , Ноам Нисан, Тим Рафгарден, Ева Тардос и Виджей В. Вазирани (2007).

Современная компьютерная арифметика Р. П. Брента и П. Циммермана.

Хьюберт Комон, Макс Дауче, Реми Гиллерон, Флоран Жакемард, Дени Лугиз, Кристоф Лодинг, Софи Тисон, Марк Томмаси: методы и приложения автоматов деревьев

«Описательная сложность, канонизация и теория определимых структур графов», Мартин Грох. Дата в рукописи: 7 марта 2013 г. Доступно по адресу: http://www.automata.rwth-aachen.de/~grohe/pub.en . (Ссылка не работает)

Спектры графов по Брауэру и Haemers . Я пришел к этой книге в виде главы 16 (написанной Спилманом) в Combinatorial Scientific Computing .

«Модели вычислений, исследующие возможности вычислений», Джон Э. Сэвидж. Доступно по адресу http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .

Теория автоматов: алгоритмический подход Хавьера Эспарза

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

Лап Чи Лау, Р. Рави и Мохит Сингх опубликовали черновик новой книги «Итерационные методы в комбинаторной оптимизации»:

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

Речь идет о методе итеративного округления: новой технике, которая может быть использована для разработки алгоритмов аппроксимации для многих задач.

Заметки или книги о распределенных алгоритмах:

• «Курс по детерминированным распределенным алгоритмам» Юкки Суомелы. Доступно по адресу http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf.
• «Принципы распределенных вычислений» Роджера Ваттенхофера. Доступно по адресу http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf.

«Логика и дискретная математика для компьютерных ученых», Джеймс Колдуэлл. Дата рукописи: 22 августа 2011 г. Доступно по адресу: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

«Структуры данных и алгоритмы, базовый инструментарий», Курт Мелхорн. Дата рукописи: август 2008 г. Доступно по адресу: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

«Введение в теорию графов и сложные сети», Мартин Ван Стин. Дата рукописи: январь 2010 г. Доступно по адресу: http://www.distributed-systems.net .

«Теория категорий для вычислительной науки», Майкл Барр и Чарльз Уэллс. Доступно по адресу http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

«Философия информатики», Уильям Дж. Раппопорт. Дата рукописи: 24 декабря 2013 г. Доступно по адресу: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

«Теория дробных графов: рациональный подход к теории графов», Эдвард Шейнерман и Даниэль Уллман. Доступно по адресу http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

«Основы науки о данных» ( pdf ) Хопкрофта и Каннана. Текст обсуждался Липтоном в его блоге. Как видно из названия, акцент текста, похоже, делается на приложениях и проблемах, связанных с проблемами больших данных и обучения. Кажется, вырос из этого курса .

(Обновление 8/2015) У книги появился третий автор, Аврим Блум. Ссылка в формате PDF была обновлена.

PlanetMath перечисляет более 150 книг, которые доступны в Интернете. Список регулярно обновляется (последнее добавление 2011-01-09, на момент написания статьи). Книги связаны с математикой, но некоторые из них полезны и в TCS.

Байесовское рассуждение и машинное обучение , Дэвид Барбер.

Сети, толпы и рынки: рассуждения о тесно связанном мире Дэвидом Исли и Джоном Кляйнбергом.

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