Какие бумаги должны прочитать все?

Этот вопрос (вдохновленный) / (позорно украденный) похож на вопрос в MathOverflow , но я ожидаю, что ответы здесь будут совсем другими.

У всех нас есть любимые статьи в наших соответствующих областях теории. Время от времени каждый находит бумагу настолько поразительной (например, важной, неотразимой, обманчиво простой и т. Д.), Что каждый хочет поделиться ею со всеми. Так что перечислите эти документы здесь! Они не должны быть из теоретической информатики - все, что, по вашему мнению, может понравиться сообществу, является хорошим ответом.

Вы можете дать столько ответов, сколько захотите; пожалуйста, положите одну бумагу за ответ ! Также обратите внимание, что это вики сообщества, поэтому голосуйте за все, что вам нравится!

(Обратите внимание, что ранее был задан вопрос о работах с теоретико-рекурсивной сложностью, но он довольно специализированный.)

«Математическая теория коммуникации» Клода Шеннона, классика теории информации. Очень читабельно.

( Зеркало )

Статья 1936 года, которая, возможно, положила начало информатике:

• Алан Тьюринг, «О вычислимых числах, с приложением к проблеме Энтшайдунгса», Труды Лондонского математического общества s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Всего лишь на 36 страницах Тьюринг формулирует (но не называет) машину Тьюринга, пересматривает знаменитую первую теорему Гёделя о неполноте в терминах вычислений, описывает концепцию универсальности и в приложении показывает, что вычислимость машинами Тьюринга эквивалентна вычислимости по определяемые функции (как изучал Черч и Клини).$\lambda$

« Размышления о доверии » Кена Томпсона . Короткий, сладкий и умопомрачительный.

Что каждый ученый должен знать об арифметике с плавающей точкой

Эта статья объясняет и усиливает представление о том, что с плавающей точкой не волшебство. Это объясняет переполнение, недостаток, что такое денормализованные числа, что такое NaN, что такое inf, и все, что они подразумевают. Прочитав эту статью, вы поймете, почему a == a + 1.0 может быть истинным, почему a == a может быть ложным, почему запуск вашего кода на двух разных машинах может дать вам два разных ответа, почему суммирование чисел в разных порядок может дать вам разность порядка величины и все дурацкие вещи, которые происходят в мире отображения бесконечно бесконечного множества чисел на счетно конечное множество.

Отредактированная версия также доступна в Интернете.

Кешава Как читать газету . Вы также можете скачать статью здесь .

Пути, деревья и цветы Дж. Эдмондса. Эта статья о классической проблеме комбинаторной оптимизации не только хорошо написана, но и утверждает, что понятие «алгоритмы полиномиального времени» по сути является синонимом эффективности.

Приводимость среди комбинаторных проблем Ричард Карп. В статье содержится то, что часто называют «оригинальными 21-полными задачами» Карпа. Во многих отношениях эта статья действительно мотивировала изучение NP-полноты, демонстрируя ее применимость к более широкой области. Очень читабельно.

Хартманис и Стернс, «О вычислительной сложности алгоритмов» , Труды Американского математического общества 117: 285–306 (1965)

Это была первая статья, в которой всерьез изучалось изучение сложности времени, и, безусловно, это стало главным стимулом для совместной премии Хьюрманиса и Стернса Тьюринга. Хотя их первоначальные определения не совсем то, что мы используем сегодня, документ остается чрезвычайно читабельным. Вы действительно чувствуете, как обстоят дела на старой границе Дикого Запада 60-х годов.

Квантово-механические компьютеры (PDF) Ричард Фейнман.

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

Затем он показывает, как любая классическая схема может быть закодирована в не зависящий от времени гамильтониан! Его доказательство распространяется и на квантовые схемы, поэтому он показывает, что эволюционирующие во времени гамильтонианы BQP-сложны! Его гамильтонова конструкция также используется в доказательстве квантовой версии теоремы Кука-Левина, доказанной Китаевым, которая показывает, что k-локальный гамильтониан является QMA-полным.

Графы расширителей и их приложения, С. Хори, Н. Линиал и А. Вигдерсон - очень хороший обзор графов расширителей. Не удивительно, что он выиграл приз AMS Conant 2008 года.

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

• алгоритм лог-пространства для ненаправленной связи (Reingold, STOC, 2005)
• альтернативное доказательство теоремы PCP (Dinur, ECCC, TR05-046, 2005)

и не так давно

• $O(\log n)$$O(n \log n)$$n$
• Линейно-временные кодируемые и декодируемые коды с исправлением ошибок (Спилман, STOC, 1995)

Сотни результатов невозможности для распределенных вычислений Фича и Рупперта. Читаемый, наглядный опрос, который действительно представляет сотни результатов невозможности, включая основные вопросы области. Замечательный фрагмент пояснительного письма.

Я удивлен тем, что никто не придумал «Некоторые оптимальные результаты неадекватности» Хастада (JACM 2001; первоначально STOC 1997). Эта знаковая статья написана так хорошо, что вы можете прийти к ней с небольшой математической зрелостью, и это заставит вас захотеть хорошо изучить несколько вещей, таких как методы Фурье, параллельное повторение, гаджеты и еще много чего.

$O((log N)^3)$$O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$

Les искателя в Теория Обучающийся (1984) установить программу для теории обучения на протяжении десятилетий, и это приятно и читаемым бумага!

В статье также есть довольно интуитивное объяснение, которое делает его увлекательным и убедительным. Различные части этого документа все еще регулярно цитируются в разговорах COLT / ALT.

Возможно, слишком простой, но я шокирован тем, что никто не упомянул оригинальные лямбда-статьи Стила и Суссмана: SCHEME: интерпретатор расширенного лямбда-исчисления , Lambda: конечный императив , Lambda: окончательный декларативный .

Рекурсивные функции символических выражений Джона Маккарти и их вычисление на машине, часть I.

Это основополагающая статья о Лиспе. Здесь мы находим первый метакруглый оценщик, помещающийся на одной странице. Его влияние невозможно переоценить, и оно все еще в высшей степени читаемо.

Сложность процедур доказательства теорем Стивена А. Кука. Эта статья доказывает, что все языки, определяемые недетерминированными машинами Тьюринга с полимитами, могут быть (Кука) сведены к набору пропозициональных тавтологий.

Важность этого результата (по крайней мере) двояка: во-первых, он показывает, что в NP существуют проблемы, которые, по крайней мере, такие же сложные, как у всего класса, NP- полные проблемы; кроме того, он предоставляет конкретный пример такой проблемы, которая затем может быть сведена к другим, чтобы доказать, что они решены.

В настоящее время сокращения Карпа используются чаще, чем сокращения Кука, но основное доказательство этой статьи легко адаптировать, чтобы показать, что SAT является NP- полной по отношению к сокращениям Карпа.

«Call-by-value» - это двойственное слово «by-by-name» от Philip Wadler.

CAR Hoare, Аксиоматическая основа для компьютерного программирования .

Из аннотации: В этой статье сделана попытка исследовать логические основы компьютерного программирования с использованием методов, которые были впервые применены при изучении геометрии, а затем были распространены на другие разделы математики.

Он имеет шесть страниц, за которыми довольно легко следить.

Алон, Матиас и Сегеди, Пространственная сложность аппроксимации частотных моментов , JCSS 58 (1): 137-147, 1999.

Эта довольно волшебная статья была первой, которая формализовала алгоритмы потоковой передачи и доказала строгие верхние и нижние оценки для основных задач в потоковой модели. Его методы просты, его доказательства прекрасны, и его влияние было глубоким. Работа получила Алон, Матиас и Сегеди премии Геделя в 2005 году.

Статья Иммермана, доказывающая теорему, теперь известную как теорема Иммермана – Селецкого, является отличным примером легко читаемой, умной и короткой статьи. Мне нравится история, рассказанная во вступлении.

Н. Иммерман, Недетерминированное пространство закрыто при дополнении, SIAM Journal of Computing 17, 1988, pp. 935–938.

$f(n) \ge \log(n)$

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right).$

$\text{NPSPACE} = \text{PSPACE}$$\text{P}$$\text{NP}$

Савич, Уолтер Дж. (1970), «Отношения между недетерминированными и детерминированными лентными сложностями», Journal of Computer and System Sciences 4 (2): 177–192.

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

Усовершенствованные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования Геманса и Уильямсона.

Прекрасный пример внедрения новой методики для получения результатов, которые намного лучше, чем известные ранее.

Экстракторы и псевдослучайные генераторы Лука Тревизан. В этой статье хороший экстрактор случайностей построен с помощью кодов с коррекцией ошибок и комбинаторных конструкций. Конструкцию довольно легко понять, но она совершенно ошеломительна, потому что совершенно не очевидно, какова связь между экстракторами, кодами и конструкциями.

В конце концов, это хороший пример результата в TCS, который требует некоторой причудливой комбинаторики.

Как написать доказательство , Лесли Лэмпорт.

Влияние переменных на булевы функции, Дж. Кан, Дж. Калай и Н. Линиал

Эта статья представила методы Фурье для сообщества TCS и решила очень аккуратную открытую проблему.

Я нахожу эту статью очень читабельной.

Если я могу процитировать Сару Пэйлин по этому вопросу: «Все они».

Более серьезно, я думаю, что большинство статей не следует читать в оригинале. Со временем люди находят лучший способ понимания и представления оригинальной проблемы / решения. За исключением оригинальной статьи Тьюринга, которая имеет историческое значение, я бы не рекомендовал читать большинство оригинальных работ, если есть последующие работы, которые очистили ее. В частности, многие вещи представлены в книгах гораздо лучше, чем в оригинале.

• Н. Хомский. Три модели для описания языка. IEEE Труды по теории информации 3. 1956 г. doi: 10.1109 / TIT.1956.1056813

Хомский анализирует, как математические модели могут использоваться для описания естественного языка с лингвистической точки зрения.

Курт Гёдель Об формально неразрешимых суждениях Principia Mathematica и родственных систем .