Хорошие примеры того, как хорошо писать в TCS

46

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

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

Правила:

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

Я надеюсь, что это может стать ресурсом, как и многие другие наши широкие вопросы. Я отмечаю это CW по этой причине.

Суреш Венкат
источник
2
PDF-версия заметок курса Кнута, Ларраби и Робертса по математическому письму распространяется по Интернету. Например, здесь: jmlr.csail.mit.edu/reviewing-papers/…
Логан Мэйфилд
3
В дополнение к комментариям Каве и Логана, Дон Кнут прочитал серию видео-лекций в Стэнфорде по программе «Математическое письмо». У меня есть видео, но я не могу найти их где-нибудь в Интернете. Я не возражаю против того, чтобы их где-то выкладывать, но я уверен, что вначале будут пробелы в авторских правах.
Винсент Руссо
9
@ VincentRusso они здесь: scpd.stanford.edu/knuth/index.jsp
Суреш Венкат

Ответы:

6

Я помню, что мне очень понравилась статья Луки, дающая спектральное приближение к Максу: http://arxiv.org/pdf/0806.1978v5.pdf .

За исключением четкого изложения, он хорошо рисует более общую картину: почему трудно приближение MaxCut лучше, чем фактор-2, почему можно ожидать, что спектральные методы могут работать, как его алгоритм связан с неравенством Чигера и с Гоманс-Уильямсон СДП. Кроме того, сам алгоритм очень аккуратен.

Сашо Николов
источник
6

Экстрактор Луки Тревизана прекрасно написан - идея в то время была революционной, и Лука излагал интуицию великолепно.

Д.С.
источник
5
Ссылка на бумагу?
Суреш Венкат
5

Не уверен, подходит ли он для TCS, но классическая статья Кляйнберга - хороший пример хорошего письма. По крайней мере, это то, что я использую в качестве примера, когда мне задают этот вопрос.

Авторитетные источники в гиперссылочной среде Джона М. Клайнберга http://www.cs.cornell.edu/home/kleinber/auth.pdf

Также весьма интересно сопоставить эту статью с «газетой Google», опубликованной в WWW. Клейнбергская статья написана намного лучше.

Панос Ипейротис
источник
4

Книга Одеда Голдрайха « В мире P = BPP» - одна из лучших написанных мной статей. Это происходит главным образом из-за ясности изложения, концептуальной перспективы и выбора, чтобы включить размышления относительно значения результатов в статье.

оборота user887
источник