¿Papeles divertidos relacionados con TCS, etc.?

¿Cuál es el trabajo publicado más divertido relacionado con TCS que conoces?

Por favor incluya solo aquellos que están destinados a ser divertidos. Se prefieren las obras que están explícitamente diseñadas para ser inteligentemente humorísticas (en lugar de, por ejemplo, una colección publicada de chistes cortos sobre teoría de la complejidad). También se aceptan trabajos con títulos humorísticos (en realidad humorísticos, no solo lindos).

Por favor, solo un trabajo por respuesta para que los "mejores" puedan llegar a la cima.

Noticia de Scott Aaronson: colapso de la jerarquía polinómica: miles temían tratables

El problema del papel higiénico (Donald Knuth, American Mathematical Monthly, 1984). De la introducción:

Los dispensadores de papel higiénico en un determinado edificio están diseñados para contener dos rollos de pañuelos, y una persona puede usar cualquiera de los rollos. Hay dos tipos de personas que usan los baños del edificio: grandes y pequeños. Un gran seleccionador siempre toma un pedazo de papel higiénico del rollo que actualmente es más grande; un pequeño selector siempre hace lo contrario. Sin embargo, cuando los dos rollos son del mismo tamaño, o cuando solo un rollo no está vacío, todos eligen el rollo no vacío más cercano. Cuando ambos rollos están vacíos, todos tienen un problema.

Kyle Burke y David Charlton. Límites inferiores para el tiempo polinómico probablemente isítico. Boston University, 2005. (Gracias a @arnab y al Web Archive por el enlace).

Estoy bastante seguro de que este fue un artículo de April Fool, pero de cualquier manera es absolutamente gracioso. El abstracto:

Llenamos un vacío en la teoría de la complejidad existente al introducir la clase de cálculos de tiempo polinomiales probablemente, es decir, cálculos que, ya sabes, probablemente terminen en tiempo polinómico, hasta donde sabemos. Aplicamos esta clase para mostrar que los algoritmos para problemas de NP completo probablemente no se ejecutan en tiempo polinómico.

Andrew W. Appel " ¿Es POPL las matemáticas o la ciencia? "

Este artículo estudia las conferencias de CS e intenta clasificarlas como teóricas o aplicadas en función de si los autores ordenan sus nombres en orden alfabético (teórico) o por contribución (aplicada).

Varios de los papeles de Jean-Yves Girard .

Su artículo de Linear Logic tiene la siguiente nota al pie del editor de la revista Theoretical Computer Science:

Debido a su extensión y novedad, este documento no ha sido sometido al proceso normal de arbitraje. El editor está preparado para compartir con el autor cualquier crítica que eventualmente se expresará con respecto a este trabajo.

Otro es Locus Solum, de las reglas de la lógica a la lógica de las reglas . El documento de 192 páginas tiene un apéndice que tiene casi 100 páginas llamado " Un desperdicio puro de papel ", el apéndice más divertido que he visto.

• La complejidad de las canciones de Don Knuth
• Sobre funciones subexponenciales superpolinomiales de Alan T. Sherman (no "Man T. Sherman" como sugiere la Biblioteca Digital ACM).

El artículo de Yonatan Bilu, Dana Porrat y Yoav Yaffe " Sobre el número de condones en una orgía barata de sexo seguro ". Este documento no fue publicado, por lo que no corresponde a uno de los requisitos (para ser publicado trabajo). Pero creo que se puede incluir aquí como una excepción.

De hecho, hay un diario completo que pretende ser divertido. La revista de craptología . Los temas suelen estar relacionados con la criptografía. También hay algunos videos de sesiones (!)

Un ejemplo es el documento de Volumen 4 de Criptografía en el Universo Hitchhiker (sección 5) es:

Próximas atracciones

Si ha disfrutado de nuestra presentación, le complacerá saber sobre las próximas atracciones del mismo autor:

- El criptoanálisis de los sistemas de protocolo interactivo humano. Un controvertido criptoanálisis del artículo de Shakira [4] que demuestra que, de hecho, HIPS miente.

- Anti-cero-conocimiento. Un sistema de protocolo que revela todo lo que un probador sabe, excepto lo que el verificador quiere escuchar. La mayoría de los servicios de atención al cliente han desarrollado protocolos ad-hoc anti-conocimiento cero.

- Distribución cuántica de claves basada en fenómenos sociales. Este artículo muestra cómo distribuir claves usando técnicas cuánticas pero sin usar objetos cuánticos. En lugar de utilizar objetos cuánticos, el protocolo utiliza la incertidumbre que tiene cualquier hombre sobre si su primera noche con una mujer cuenta como una fecha o no para transmitir las claves.

Matemáticas concretas: una base para la informática , por Ronald Graham, Donald Knuth y Oren Patashnik.

Un libro increíble con muchas notas secundarias divertidas. :) (Véase también la página GKP de DEK ).

Recomendaría los procesamientos de FUN: la Conferencia Internacional sobre Diversión con Algoritmos.

Debo decir que "La dureza del juego de Lemmings, o Oh, no, más pruebas de integridad de NP" de Graham Cormode es una de mis favoritas.

La propuesta terminológica de Don Knuth . SIGACT News, 6 (1), 1974. Mencionado en The Complexity Blog. Aparentemente, aquí es donde obtuvimos los términos "NP-complete" y "NP-hard".

Uno de mis favoritos de esta pieza es la sugerencia de Albert Meyer de que lo que ahora llamamos problemas NP-hard se denominará Hard-as-Satisfiability, o hard-as-S para abreviar.

Echa un vistazo a la figura que acompaña al documento de SODA de 1 página de Adam Kalai, "Generando números aleatorios factorizados, fácilmente": enlace

El artículo de Mihai Patrascu y Liam Roditty sobre " Oráculos de distancia más allá del límite de Thorup-Zwick " se tituló inicialmente " Cómo hacer crecer tus bolas " en la página de inicio de Mihai :-)

A. Broder, J. Stolfi " Algoritmos pesimales y análisis de simplexidad ", ACM SIGACT News 16 (3), Otoño 1984.

El documento presenta "una rama completamente nueva de la informática, el diseño y el análisis de algoritmos reacios. Intuitivamente, un algoritmo reacio para un problema P es uno que desperdicia tiempo de una manera lo suficientemente ingeniosa para engañar a un observador ingenuo".

El Parlamento a tiempo parcial de Lamport hizo un gran avance en la informática distribuida, pero el documento estaba tan (¡a propósito!) Confundido que la gente no podía entenderlo, que yo sepa, le tomó alrededor de 10 años publicarlo (editores anteriores) en su forma ofuscada. Finalmente, Lamport siguió con Paxos Made Simple , que tenía el siguiente resumen: " El algoritmo de Paxos, cuando se presenta en inglés simple, es muy simple ".

La Asociación para la Herejía Computacional en CMU tiene varios de estos, que se presentan en la conferencia anual SIGBOVIK (que se realizará el próximo 01/04/2011). Mi favorito personal es:

Un enfoque basado en el robo para la adquisición de objetos en 3D.

Con el mismo espíritu que la publicación de Murilo da Silva, no puedo resistirme a publicar este extracto de "Factoring N-Cycles and Counting Maps of Género dado" de Goupil y Schaefer :

Después de esta prueba, alentamos amablemente al lector a que haga una pausa y disfrute de una actividad más ligera, como la observación de aves o la jardinería, antes de continuar con la lectura.

"Refinamiento en el formalismo basado en el estado" por Lamport.

Un amigo nuestro, que era un matemático brillante, ha sido hospitalizado por abuso a largo plazo de drogas alucinógenas. Decidimos darle un reloj digital para su habitación. Sin embargo, su médico sugiere que la visualización de la hora y los minutos juntos podría ser demasiado confusa. Entonces, colocamos cinta adhesiva sobre la pantalla de minutos, convirtiendo nuestro regalo en un reloj digital de horas.

Acabo de descubrir "Una carta del autor frustrado de un artículo de revista" . Buena lectura ;-)

Me encontré con el "Flash de la teoría de la complejidad" en algún momento, y pensé que era bastante divertido.

Títulos divertidos recientes:

• A. Kehagias, P. Pralat, Algunos comentarios sobre policías y ladrones borrachos , Theoretical Computer Science 463 (2012) 133-147, DOI

• A. Kehagias, D. Mitsche, P. Pralatb, Policías y ladrones invisibles: El costo de la embriaguez , Theoretical Computer Science (2013), en prensa

• Natasha Komarov, Peter Winkle, Capturando al ladrón borracho en un gráfico , mayo de 2013, arXiv: 1305.4559

Mick obtiene algunos (las probabilidades están de su lado) por Reed Chvatal y Chvatal Reed (FOCS 1992), por satisfacción (también conocida como satisfacción).

¿Cuánto daño podría causar un crítico crítico que tiene un mal día? Divertidas reseñas ficticias de viejos y famosos artículos de CS.

El discurso de Alice and Bob After Dinner de John Gordon.

Buena charla alegre sobre la teoría de la codificación.

Sobre otro tema ( ¿Cómo arbitro un trabajo? ), Encontré el siguiente trabajo:

Graham Cormode. 2009. Cómo NO revisar un artículo: las herramientas y técnicas del revisor adversario. SIGMOD Rec . 37, 4 (marzo de 2009), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

Me divertí mucho leyendo este periódico;)

Bruce Reed, Mangos y Arándanos , Combinatorica 19 (1999) 267-296.

Ahora no puedo pensar en un papel divertido, pero sí recuerdo un papel "normal" que tenía una línea divertida. De hecho, fue la primera oración en la Sección 1. Los autores comenzaron el trabajo con:

"Contrariamente a nuestra práctica habitual, nos sentimos obligados a comenzar este trabajo con algunas definiciones". Así que deja que G ... "

El título del documento es " $beta$gráficos perfectos", de Markossian, Gasparian y Reed en 1996. Me llamó la atención porque de hecho es un documento clave sobre la teoría de gráficos perfectos, donde se define la clase de gráficos beta perfectos, una clase que es análoga a las gráficas perfectas (las gráficas perfectas beta son una subclase de gráficas EVEN sin agujeros, mientras que las gráficas perfectas son una subclase de gráficas libres de agujeros ODD.

En cuanto a un título divertido: "Cómo jugar un juego de colorear contra un adversario daltónico"

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

¿Qué tal Scott no siempre es sobrio ?

Lambda the Ultimate me llamó la atención el documento técnico sobre Fósforo, el Popular Lisp , que si "Popular Lisp" no te avisaba, es satírico ^ _-