¿Qué innovaciones en la teoría de CS de los últimos 10 años han tenido un impacto fuera de la academia? Si iba a hacer un doctorado en CS, ¿debería hacer teoría en lugar de aprendizaje automático?

Un tema que viene a la mente son las tablas hash distribuidas : estas solo han sido realmente un tema de investigación durante los últimos 10-15 años, pero juegan un papel muy importante en muchos sistemas prácticos, como Bittorrent.

Estoy seguro de que hay otros, pero no puedo pensar en ningún otro gran ejemplo en este momento. Personalmente sospecho que si su objetivo es tener un gran impacto en la industria en un plazo de <10 años, probablemente sea mejor que vaya directamente a la industria. La academia, en el mejor de los casos, parece ser un lugar que se esfuerza por encontrar ideas verdaderamente novedosas que eventualmente se vuelvan prácticas y generalizadas en una escala de tiempo más larga: uno de mis ejemplos favoritos aquí es todo el trabajo que se dedicó a la construcción de JIT para Smalltalk y Uno mismo en los años 80 y 90, y que finalmente ahora están llegando a la corriente principal en HotSpot JVM y más recientemente en v8 y otros motores Javascript.

Bien, veamos.

• Los filtros Bloom son una técnica inteligente que brinda soluciones prácticas para una amplia variedad de problemas. La idea básica se inventó por primera vez en 1970 y tuvo una aplicación práctica a lo largo de las décadas desde entonces, pero los teóricos la retomaron alrededor de 2000 y han ideado una larga línea de variaciones que han hecho que los filtros Bloom sean útiles (y de hecho utilizados) para muchos más diversos. Tareas. Ver [1] para una encuesta.
• Los algoritmos de transmisión son un área de la teoría de CS que ha producido una gran cantidad de algoritmos novedosos que hacen que el análisis de grandes conjuntos de datos sea manejable. El nombre fue acuñado hace unos 15 años en un artículo de Alon, Matias y Szegedy; Gran parte del trabajo se realizó en la última década. Los enrutadores de red y otros dispositivos que procesan flujos de datos gigantes utilizan estos algoritmos por necesidad. Consulte el artículo de Wikipedia [2] para obtener una descripción general y muchos enlaces.
• Criptografía basada en celosía y criptografía post-cuántica en general: esta es un área cuyo gran impacto en el mundo real aún no ha sucedido, pero es inusual que podamos estar bastante seguros de que sucederá. Las computadoras cuánticas llegarán en las próximas décadas. Cuando lo hagan, facilitarán la factorización de números y el cálculo de logaritmos discretos, destruyendo la seguridad de muchos de los criptosistemas más utilizados que protegen Internet. La última década ha visto una gran cantidad de trabajo en otras familias de criptosistemas, con un enfoque en llevarlos a la práctica para que, a medida que se desarrolle la computación cuántica, estemos listos para usarlos. Ver http://pqcrypto.org/ y en particular [3]. Como beneficio adicional, algunos de estos sistemas criptográficos tienen una aplicación práctica hoy en día, incluso sin la amenaza de las computadoras cuánticas.
• Las tablas hash distribuidas , como señaló Nelson, son otro buen ejemplo. En lugar de duplicar su descripción, solo agregaré un par de enlaces: el artículo de Wikipedia [4] por falta de una mejor encuesta, y uno de los primeros artículos [5].

Estos son solo algunos ejemplos que conozco por las personas que conozco y las cosas que me interesaban cuando estaba en la academia; Alguien que realmente haya seguido bien el campo sin duda podría producir una lista mucho más larga.

Entonces, volviendo a sus preguntas de seguimiento, ¿importa la informática teórica? Sí , algo de eso definitivamente lo hace. Algunas investigaciones de aprendizaje automático también son importantes.

¿Deberías entrar en esto como una carrera? Si le interesa el impacto práctico, probablemente no. Los incentivos en la academia no recompensan el impacto práctico, y usted debe moverse constantemente contra la corriente si desea trabajar para lograr ese impacto. He observado esto no solo en teoría, sino también en sistemas, donde los estudiantes graduados hacen cosas como escribir sistemas operativos desde cero en C y ensamblar, y que puede parecer lo más alejado de la teoría que es posible. Así que dudo que sea diferente en el aprendizaje automático tampoco.

En cambio, si su objetivo es tener un gran impacto, probablemente debería dirigirse a Silicon Valley . Aquí se trata del impacto práctico, hay muchas personas ambiciosas para cambiar una industria o el mundo, y algunas lo hacen.

[1] Andrei Broder y Michael Mitzenmacher. “Aplicaciones de red de filtros Bloom: una encuesta” (2005). http://www.eecs.harvard.edu/~mic …
[2] http://en.wikipedia.org/wiki/Str …
[3] DJ Bernstein. “Introducción a la criptografía post-cuántica” (2009). http://pqcrypto.org/www.springer …
[4] http://en.wikipedia.org/wiki/Dis …
[5] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek y Hari Balakrishnan. “Acorde: un servicio de búsqueda escalable de igual a igual para aplicaciones de Internet” (2001). http://pdos.csail.mit.edu/papers …