Qual é o trabalho publicado mais engraçado sobre TCS que você conhece?
Por favor, inclua apenas aqueles que pretendem ser engraçados. Os trabalhos explicitamente criados para serem inteligentemente bem-humorados (em vez de, digamos, uma coleção publicada de piadas curtas sobre a teoria da complexidade) são os preferidos. Trabalhos com títulos engraçados (na verdade engraçados, não apenas engraçados) também são aceitos.
Por favor, apenas um trabalho por resposta para que os "melhores" possam chegar ao topo.
reference-request
soft-question
big-list
Joshua Grochow
fonte
fonte
Respostas:
Jornal de Scott Aaronson: Hierarquia polinomial desmorona: milhares temiam ser tratáveis
fonte
O Problema do Papel Higiênico (Donald Knuth, American Mathematical Monthly, 1984). Desde a introdução:
fonte
Kyle Burke e David Charlton. Limites inferiores por tempo polinomial provavelmente isístico. Universidade de Boston, 2005. (Obrigado ao @arnab e ao Web Archive pelo link.)
Tenho certeza de que este foi um artigo do April Fool, mas de qualquer forma é absolutamente hilário. O resumo:
fonte
Andrew W. Appel, " O POPL é Matemática ou Ciência? "
Este trabalho estuda as conferências de CS e tenta classificá-las como teóricas ou aplicadas com base em se os autores ordenam seus nomes em ordem alfabética (teórica) ou por contribuição (aplicada).
fonte
Vários documentos de Jean-Yves Girard .
Seu artigo Linear Logic tem a seguinte nota de rodapé do editor da revista Theoretical Computer Science:
Outro é o Locus Solum, das regras da lógica à lógica das regras . O artigo de 192 páginas possui um apêndice com quase 100 páginas chamado " Um desperdício puro de papel ", o apêndice mais engraçado que eu já vi.
fonte
fonte
O artigo de Yonatan Bilu, Dana Porrat e Yoav Yaffe " Sobre o número de preservativos em uma orgia barata de sexo seguro ". Este artigo não foi publicado e, portanto, não corresponde a um dos requisitos (trabalho a ser publicado). Mas acho que pode ser incluído aqui como uma exceção.
fonte
De fato, existe todo um diário que se destina a ser engraçado. O jornal de craptologia . Os tópicos geralmente estão relacionados à criptografia. Existem também algumas sessões de vídeos (!)
Um exemplo é o artigo do Volume 4 de Criptografia no Universo de um Mochileiro (seção 5):
fonte
Matemática Concreta: Uma Fundação para Ciência da Computação , de Ronald Graham, Donald Knuth e Oren Patashnik.
Um livro incrível com muitas notas laterais engraçadas. :) (Veja também a página GKP do DEK .)
fonte
Eu recomendaria os processamentos da FUN: a Conferência Internacional sobre Diversão com Algoritmos.
Devo dizer que "A dureza do jogo Lemmings, ou Oh não, mais provas de completude de NP" de Graham Cormode é uma das minhas favoritas.
fonte
Uma proposta terminológica de Don Knuth . SIGACT News, 6 (1), 1974. Mencionado no The Complexity Blog. Aparentemente, foi aqui que obtivemos os termos "NP-complete" e "NP-hard".
Uma das minhas favoritas desta peça é a sugestão de Albert Meyer de que o que chamamos agora de problemas de NP-hard seja chamado de Hard-as-Satisfiability, ou hard-as-S, para abreviar.
fonte
Confira a figura que acompanha o artigo SODA de 1 página de Adam Kalai, "Gerando números fatorados aleatórios facilmente": link
fonte
O artigo de Mihai Patrascu e Liam Roditty sobre " Oráculos a Distância Além do Limite de Thorup-Zwick " foi inicialmente intitulado " Como fazer crescer suas bolas " na página inicial de Mihai :-)
fonte
A. Broder, J. Stolfi " Algoritmos pessimais e análise de simplicidade ", ACM SIGACT News 16 (3), outono de 1984.
O artigo introduz "um ramo inteiramente novo da Ciência da Computação, o design e a análise de algoritmos relutantes. Intuitivamente, um algoritmo relutante para um problema P é aquele que perde tempo de uma maneira que é suficiente para enganar um observador ingênuo".
fonte
O parlamento de Lamport em tempo parcial fez um avanço na computação distribuída, mas o artigo ficou tão (intencionalmente) ofuscado que as pessoas não conseguiam entendê-lo - até onde eu sei, ele levou cerca de 10 anos para publicá-lo (editores anteriores) em sua forma ofuscada. Eventualmente, Lamport seguiu Paxos Made Simple , que tinha o seguinte resumo: " O algoritmo Paxos, quando apresentado em inglês simples, é muito simples ".
fonte
A Associação de Heresia Computacional da CMU tem vários deles, que são apresentados na conferência anual do SIGBOVIK (realizada em 04/01/2011). Meu favorito pessoal é:
Uma abordagem baseada em roubo para aquisição de objetos em 3D.
fonte
No mesmo espírito do post de Murilo da Silva, não resisto a publicar este trecho dos "Ciclos N de factoring e mapas de contagem de gêneros" de Goupil e Schaefer :
fonte
"Refinamento no formalismo baseado no Estado", de Lamport.
fonte
Acabei de descobrir "Uma carta do autor frustrado de um jornal" . Boa leitura ;-)
fonte
Me deparei com o "Complexity Theory Newsflash" em algum momento e achei muito engraçado.
fonte
Títulos engraçados recentes:
A. Kehagias, P. Pralat, Algumas observações sobre policiais e ladrões bêbados , Ciência da Computação Teórica 463 (2012) 133-147, DOI
A. Kehagias, D. Mitsche, P. Pralatb, Policiais e ladrões invisíveis: O custo da embriaguez , Teoria da Computação (2013), na Imprensa
Natasha Komarov, Peter Winkle, Capturando o ladrão bêbado em um gráfico , maio de 2013, arXiv: 1305.4559
fonte
Mick recebe algumas (as probabilidades estão do seu lado) por
ReedChvatal eChvatalReed (FOCS 1992), sobre satisfação (aka satisfação).fonte
Quanto dano pode ser causado por um revisor que está tendo um dia ruim? Revisões fictícias hilariantes de papéis velhos famosos do CS.
fonte
O discurso de Alice e Bob depois do jantar de John Gordon.
Boa conversa descontraída sobre a teoria da codificação.
fonte
Em outro tópico ( como faço para arbitrar um artigo? ), Encontrei o seguinte artigo:
Graham Cormode. 2009. Como NÃO revisar um trabalho: as ferramentas e técnicas do revisor adversário. SIGMOD Rec . 37, 4 (março de 2009), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122
Eu me diverti muito lendo este artigo;)
fonte
Bruce Reed, Mangas e Blueberries , Combinatorica 19 (1999) 267-296.
fonte
Agora não consigo pensar em um artigo engraçado, mas me lembro de um artigo "normal" que continha uma linha engraçada. Foi de fato a primeira frase da Seção 1. Os autores começaram o artigo com:
"Ao contrário da nossa prática usual, nos sentimos obrigados a começar este trabalho com algumas definições". Então deixe G ... "
O título do artigo é "
$beta$
-perfect graphs", de Markossian, Gasparian e Reed, em 1996. Ele chamou minha atenção porque é de fato um artigo-chave sobre a teoria perfeita dos grafos, onde é definida a classe de gráficos beta-perfeitos, uma classe que é, de certa forma, análoga aos gráficos perfeitos (os gráficos beta-perfeitos são uma subclasse dos gráficos sem buracos no EVEN, enquanto os gráficos perfeitos são uma subclasse dos gráficos sem buracos no ODD.fonte
Quanto a um título engraçado: "Como jogar um jogo de colorir contra um adversário daltônico"
http://portal.acm.org/citation.cfm?id=1137865
fonte
Que tal Scott nem sempre é sóbrio ?
fonte
Lambda the Ultimate chamou a minha atenção o whitepaper sobre Fósforo, o Popular Lisp , que se "Popular Lisp" não lhe der uma dica, é satírico ^ _-
fonte