¿Qué documentos deberían leer todos?

Esta pregunta es (inspirada por) / (vergonzosamente robada) una pregunta similar en MathOverflow , pero espero que las respuestas aquí sean bastante diferentes.

Todos tenemos trabajos favoritos en nuestras propias áreas teóricas. De vez en cuando, uno encuentra un papel tan sorprendente (por ejemplo, importante, convincente, aparentemente simple, etc.) que uno quiere compartirlo con todos. ¡Así que enumere estos documentos aquí! No tienen que ser de informática teórica: cualquier cosa que creas que podría atraer a la comunidad es una buena respuesta.

Puedes dar tantas respuestas como quieras; ¡por favor ponga un papel por respuesta ! Además, tenga en cuenta que esto es wiki comunitario, ¡así que vote por todo lo que quiera!

(Tenga en cuenta que ha habido una pregunta previa sobre artículos en complejidad teórica de recursión pero que es bastante especializada).

"Una teoría matemática de la comunicación" de Claude Shannon, clásicos de la teoría de la información. Muy legible

( Espejo )

El artículo de 1936 que posiblemente inició la informática en sí:

• Alan Turing, "Sobre números computables, con una aplicación al problema Entscheidungs", Actas de la London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

En solo 36 páginas, Turing formula (pero no nombra) la Máquina de Turing, reformula el famoso Primer teorema de incompletitud de Gödel en términos de computación, describe el concepto de universalidad y en el apéndice muestra que la computabilidad de las máquinas de Turing es equivalente a la computabilidad de funciones definibles (según lo estudiado por Church y Kleene).$\lambda$

" Reflexiones sobre la confianza en la confianza " de Ken Thompson . Corto, dulce y alucinante.

Lo que todo informático debe saber sobre la aritmética de coma flotante

Este artículo explica y refuerza la noción de que el punto flotante no es mágico. Explica el desbordamiento, el subflujo, qué son los números desnormalizados, qué son los NaN, qué es inf y todas las cosas que implican. Después de leer este documento, sabrá por qué a == a + 1.0 puede ser verdadero, por qué a == a puede ser falso, por qué ejecutar su código en dos máquinas diferentes puede darle dos respuestas diferentes, por qué sumar números en una diferente el orden puede darle un orden de diferencia de magnitud y todas las cosas extrañas que suceden en el mundo de mapear un conjunto infinitamente infinito de números en un conjunto finito contable.

Una versión editada también está disponible en la web.

Cómo leer un periódico de Keshav . También puede descargar el documento desde aquí .

Caminos, árboles y flores de J. Edmonds. Este artículo sobre el problema clásico de optimización combinatoria no solo está bien escrito, sino que también establece que la noción de "algoritmos de tiempo polinomial" es esencialmente un sinónimo de eficiencia.

Reducibilidad entre problemas combinatorios por Richard Karp. El documento contiene lo que a menudo se conoce como "los 21 problemas originales de NP completos" de Karp. En muchos sentidos, este documento realmente motivó el estudio de la integridad de NP al demostrar su aplicabilidad a un dominio más amplio. Muy legible

Hartmanis y Stearns, "Sobre la complejidad computacional de los algoritmos" , Transactions of the American Mathematical Society 117: 285–306 (1965)

Este fue el primer artículo que tomó en serio el estudio de la complejidad del tiempo, y seguramente fue el impulso principal para el premio Turing conjunto de Hartmanis y Stearns. Si bien sus definiciones iniciales no son exactamente lo que usamos hoy, el documento sigue siendo extremadamente legible. Realmente tienes la sensación de cómo eran las cosas en la antigua frontera del "Salvaje Oeste" de los años 60.

Computadoras Mecánicas Cuánticas (PDF) por Richard Feynman.

Presenta la idea de la computación cuántica, describe los circuitos cuánticos, explica cómo los circuitos clásicos pueden ser simulados por los circuitos cuánticos, y muestra cómo los circuitos cuánticos pueden calcular funciones sin muchos qubits de basura (usando la computación).

Luego muestra cómo cualquier circuito clásico puede codificarse en un Hamiltoniano independiente del tiempo. Su prueba también se aplica a los circuitos cuánticos, por lo tanto, muestra que los Hamiltonianos en evolución en el tiempo son difíciles de BQP. Su construcción hamiltoniana también se utiliza en la prueba de la versión cuántica del teorema de Cook-Levin, probada por Kitaev, que muestra que el hamiltoniano k-local es QMA completo.

Gráficos expansores y sus aplicaciones, S. Hoory, N. Linial y A. Wigderson es una encuesta extremadamente agradable sobre gráficos expansores. No sorprende que haya ganado el Premio AMS Conant 2008.

Quiero recordar que los gráficos de expansión son el ingrediente clave en los avances recientes en TCS, por ejemplo.

• algoritmo de espacio de registro para conectividad no dirigida (por Reingold, STOC, 2005)
• la prueba alternativa del teorema de PCP (por Dinur, ECCC, TR05-046, 2005)

y no tan reciente:

• $O(\log n)$$O(n \log n)$$n$
• Códigos de corrección de errores codificables y decodificables en tiempo lineal (por Spielman, STOC, 1995)

Cientos de resultados de imposibilidad para computación distribuida por Fich y Ruppert. Una encuesta pictórica legible que realmente presenta cientos de resultados imposibles, incluidas las preguntas centrales del campo. Una notable pieza de escritura expositiva.

Me sorprende que a nadie se le ocurran los "Algunos resultados óptimos de inaproximabilidad" de Hastad (JACM 2001; originalmente STOC 1997). Este documento histórico se ha escrito tan bien que puede llegar a él con poco más que madurez matemática y le hará querer aprender varias cosas bien, como sus técnicas de Fourier, repetición paralela, dispositivos y demás.

$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)$

La Teoría de lo aprendible de Les Valiant (1984) estableció la agenda de la teoría del aprendizaje durante décadas, ¡y es un documento agradable y legible!

También hay una explicación bastante intuitiva en el documento que lo hace divertido y convincente. Varias partes de este documento todavía se citan habitualmente en las conversaciones COLT / ALT.

Quizás demasiado básico, pero me sorprende que nadie haya mencionado los documentos originales de Lambda de Steele y Sussman: ESQUEMA: un intérprete para el cálculo extendido de Lambda , Lambda: el imperativo supremo , Lambda: la declaración definitiva .

Funciones recursivas de John McCarthy de expresiones simbólicas y su cálculo por máquina, parte I.

Este es el documento fundamental sobre Lisp. Aquí encontramos el primer evaluador metacircular, que cabe en una sola página. Su impacto no puede ser exagerado, y aún es muy fácil de leer.

La complejidad de los procedimientos de prueba de teoremas de Stephen A. Cook. Este artículo demuestra que todos los lenguajes decididos por las máquinas de Turing no deterministas de polytime pueden reducirse (Cook-) al conjunto de tautologías proposicionales.

La importancia de este resultado es (al menos) doble: primero, muestra que existen problemas en NP que son al menos tan difíciles como toda la clase, los problemas completos de NP ; Además, proporciona un ejemplo concreto de tal problema, que luego puede reducirse a otros para demostrar que están completos.

Hoy en día, las reducciones de Karp se usan más comúnmente que las reducciones de Cook, pero la prueba principal de este documento se puede adaptar fácilmente para mostrar que SAT es NP- completo con respecto a las reducciones de Karp.

Call-by-value es dual a call-by-name de Philip Wadler es una buena lectura.

CAR Hoare, una base axiomática para la programación de computadoras .

Del resumen: en este artículo se intenta explorar los fundamentos lógicos de la programación de computadoras mediante el uso de técnicas que se aplicaron primero en el estudio de la geometría y luego se extendieron a otras ramas de las matemáticas.

Tiene seis páginas que son bastante fáciles de seguir.

Alon, Matias y Szegedy, La complejidad espacial de aproximar los momentos de frecuencia , JCSS 58 (1): 137-147, 1999.

Este papel bastante mágico fue el primero en formalizar algoritmos de transmisión y probar rigurosos límites superiores e inferiores para tareas fundamentales en el modelo de transmisión. Sus técnicas son simples, sus pruebas son hermosas y su impacto ha sido profundo. El trabajo le valió a Alon, Matias y Szegedy el Premio Gödel en 2005.

El artículo de Immerman que prueba el teorema ahora conocido como el teorema Immerman-Szelepcsényi, es un gran ejemplo de papel fácil de leer, inteligente y corto. Me encanta la historia contada en la introducción.

N. Immerman, El espacio no determinista está cerrado bajo complementación, SIAM Journal on 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}$

Savitch, Walter J. (1970), "Relaciones entre complejidades de cinta no deterministas y deterministas", Journal of Computer and System Sciences 4 (2): 177-192.

Russell Impagliazzo's A Personal View of Average-Case Complexity . Este es un gran trabajo porque está escrito de manera inteligente y resume el estado de cosas en cinco "mundos" donde nuestras conjeturas sobre la complejidad se resuelven de varias maneras, dando consecuencias en el mundo real en cada caso.

Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacción utilizando programación semidefinida de Goemans y Williamson.

Un buen ejemplo de la introducción de una nueva técnica para obtener resultados que son mucho mejores que los conocidos anteriormente.

Extractores y generadores pseudoaleatorios de Luca Trevisan. En este documento, el buen extractor de aleatoriedad se construye mediante códigos de corrección de errores y diseños combinatorios. La construcción es bastante fácil de entender, pero es completamente sorprendente, porque no es obvio en absoluto cuál es la conexión entre extractores, códigos y diseños.

Después de todo, es un buen ejemplo de un resultado en TCS que requiere algunos combinatorios sofisticados.

Cómo escribir una prueba , por Leslie Lamport.

La influencia de las variables en las funciones booleanas, J. Kahn, G. Kalai y N. Linial

Este documento introdujo técnicas de Fourier para la comunidad TCS y resolvió un problema abierto muy claro.

Este artículo me parece muy legible.

Si puedo citar a Sarah Palin sobre este tema: "Todos ellos".

Más en serio, creo que la mayoría de los documentos no deberían leerse en el original. A medida que pasa el tiempo, la gente descubre una mejor manera de entender y presentar el problema / solución original. Excepto por el documento original de Turing, que es de importancia histórica, no recomendaría leer la mayoría de los documentos originales si hay un trabajo de seguimiento que lo haya limpiado. En particular, muchas cosas se presentan mucho mejor en los libros que en el original.

• N. Chomsky. Tres modelos para la descripción del lenguaje. IEEE Transactions on Information Theory 3. 1956. doi: 10.1109 / TIT.1956.1056813

Chomsky analiza cómo los modelos matemáticos pueden usarse para describir el lenguaje natural, desde un punto de vista lingüístico.

Sobre las proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados de Kurt Gödel .