Смешные документы, связанные с TCS и т. Д.?

Какая самая смешная опубликованная работа, связанная с TCS, вы знаете?

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

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

Газета Скотта Ааронсона: Полиномиальная иерархия рушится: тысячи боятся поддающихся контролю

Проблема туалетной бумаги (Дональд Кнут, Американский математический месяц, 1984). Из введения:

Диспенсеры для туалетной бумаги в определенном здании рассчитаны на два рулона тканей, и человек может использовать любой рулон. Есть две категории людей, которые используют комнаты отдыха в здании: большие и маленькие. Большой выбор всегда берет кусок туалетной бумаги из рулона, который в настоящее время больше; маленький выбор всегда делает обратное. Однако, когда два рулона имеют одинаковый размер, или когда только один рулон не пуст, каждый выбирает ближайший непустой рулон. Когда оба рулона пусты, у всех есть проблемы.

Кайл Берк и Дэвид Чарлтон. Нижние оценки для вероятностно-полиномиального времени. Бостонский университет, 2005. (Спасибо @arnab и веб-архиву за ссылку.)

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

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

Эндрю В. Аппель " POPL математика или наука? "

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

Несколько работ Жана-Ива Жирара .

Его статья « Линейная логика» имеет следующую сноску редактора журнала «Теоретическая информатика»:

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

Другой - это Locus Solum, от правил логики до логики правил . 192-страничная статья содержит приложение длиной почти 100 страниц под названием « Чистая трата бумаги », самое смешное приложение, которое я когда-либо видел.

• Сложность песен Дона Кнута
• О суперполиномиальных субэкспоненциальных функциях Алана Т. Шермана (не «Ман Т. Шерман», как предлагает цифровая библиотека ACM).

Доклад Йонатана Билу, Даны Поррат и Йоава Яффе " О количестве презервативов на дешевой оргии с безопасным сексом ". Эта статья не была опубликована, поэтому она не соответствует одному из требований (подлежит публикации работа). Но я думаю, что это может быть включено сюда как исключение.

На самом деле есть целый журнал, который должен быть забавным. Журнал craptology . Темы обычно связаны с криптографией. Есть также несколько видео сессий (!)

Одним из примеров является статья 4 тома « Криптография во вселенной автостопщика» (раздел 5):

Coming Достопримечательности

Если вам понравилась наша презентация, вам будет приятно узнать о предстоящих достопримечательностях того же автора:

- Криптоанализ человеческих интерактивных протокольных систем. Спорный криптоанализ работы Шакиры [4], который доказывает, что HIPS на самом деле лгут.

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

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

Конкретная математика: Фонд компьютерных наук , автор Рональд Грэм, Дональд Кнут и Орен Паташник.

Удивительная книга с множеством забавных заметок. :) (Смотрите также ДЭК «s GKP стр.)

Я бы порекомендовал процесс FUN: международную конференцию «Fun with Algorithms».

Я должен сказать, что «Трудность игры Леммингов, или нет, больше доказательств NP-полноты» Грэма Кормода - одна из моих любимых.

Терминологическое предложение Дона Кнута . SIGACT News, 6 (1), 1974. Упоминается в блоге сложности. Это, очевидно, где мы получили термины «NP-полный» и «NP-жесткий».

Одно из моих любимых произведений из этой статьи - предложение Альберта Мейера о том, что то, что мы сейчас называем NP-трудными задачами, для краткости называется трудной как удовлетворенность или жесткой как S.

Посмотрите на рисунок, который сопровождает одностраничную статью Адама Калаи SODA «Легко генерировать случайные факторные числа»: ссылка

Бумага Михая Патраску и Лиама Родитти « Дистанционные оракулы за пределами Thorup-Zwick Bound » была первоначально озаглавлена ​​« Как вырастить свои яйца » на домашней странице Михая :-)

А. Бродер, Дж. Столфи " Пессимальные алгоритмы и анализ симплексности ", ACM SIGACT News 16 (3), осень 1984 г.

В статье вводится «совершенно новая отрасль информатики, разработка и анализ неохотных алгоритмов. Интуитивно понятно, что неохотный алгоритм для задачи P - это тот, который напрасно тратит время таким способом, который достаточно изобретателен, чтобы одурачить наивного наблюдателя».

Парламент неполного рабочего дня Лампорта сделал прорыв в распределенных вычислениях, но статья была настолько (нарочно!) Запутана, что люди не могли ее понять - насколько я знаю, ему понадобилось около 10 лет, чтобы опубликовать ее (бывшие редакторы) в его запутанном виде. В конце концов Лэмпорт разработал « Paxos Made Simple» , у которого было следующее резюме: « Алгоритм Paxos, представленный простым языком, очень прост ».

У Ассоциации вычислительной ереси при КМУ есть ряд таких, которые представлены на ежегодной конференции SIGBOVIK (следующая состоится 04/01/2011). Мой личный фаворит это:

Кража подхода к приобретению 3D-объектов.

В том же духе, что и пост Мурило да Силвы, я не могу удержаться от публикации этой выдержки из «Факторинга N-циклов и карт подсчета данного рода» Гупиля и Шефера :

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

«Уточнение в государственном формализме» Лампорта.

Наш друг, который был блестящим математиком, был госпитализирован из-за длительного злоупотребления галлюциногенными наркотиками. Мы решили дать ему цифровые часы для своей комнаты. Тем не менее, его врач предполагает, что отображение часов и минут вместе может быть слишком запутанным. Итак, мы поместили ленту на дисплей минут, превратив наш подарок в цифровые часы.

Я только что обнаружил «Письмо от разочарованного автора журнальной газеты» . Приятно читать ;-)

В какой-то момент я наткнулся на «Новость о теории сложности» и подумал, что это довольно забавно.

Последние смешные заголовки:

• А. Кехаджиас, П. Пралат, Некоторые замечания о полицейских и пьяных грабителях , Теоретическая информатика 463 (2012) 133-147, DOI

• А. Кехаджиас, Д. Митче, П. Пралатб, Копы и невидимые грабители: цена пьянства , Теоретическая информатика (2013), в печати

• Наташа Комаров, Питер Винкль, Захват пьяного грабителя на графике , май 2013 г., arXiv: 1305.4559

Мик получает некоторые (шансы на его стороне) от Reed Chvatal и Chvatal Рид (FOCS 1992), на удовлетворение (ака выполнимости).

Какой ущерб может быть причинен плохому дню у рецензента? Веселые вымышленные обзоры знаменитых старых работ CS.

Алиса и Боб после обеда Речь Джона Гордона.

Хороший беззаботный разговор по теории кодирования.

По другой теме ( Как мне судить статью? ) Я нашел следующую статью:

Грэм Кормод. 2009. Как НЕ рецензировать статью: инструменты и методы состязательного рецензента. SIGMOD Rec . 37, 4 (март 2009 г.), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

Мне было очень весело читать эту статью;)

Брюс Рид, Манго и черника , Combinatorica 19 (1999) 267-296.

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

«Вопреки нашей обычной практике, мы считаем необходимым начать эту статью с нескольких определений». Так пусть Г ... »

В $beta$1996 году Марксосян, Гаспарян и Рид назвали статью « -совершенные графы». Она привлекла мое внимание, поскольку на самом деле это ключевая статья по теории совершенных графов, в которой определен класс бета-совершенных графов, класс, аналогичный совершенным графам (бета-совершенные графы являются подклассом графов без дыр, в то время как совершенные графы являются подклассом графов без дыр в ODD).

Насколько забавный заголовок: «Как играть в раскраску против дальтоника»

http://portal.acm.org/citation.cfm?id=1137865

Как насчет Скотта не всегда трезвый ?

Lambda the Ultimate привлекла мое внимание к «Фосфору» , «Популярному Лиспу» , который, если «Популярный Лисп» вас не опроверг, является сатирическим ^ _-