¿Ha habido nuevos algoritmos brillantes de informática en los últimos 10 años?

Cifrado totalmente homomórfico (FHE)
Imagínese si fuera un hospital que necesitara procesar / analizar datos en EC2, pero estuviera preocupado por la privacidad. En un mundo ideal, a uno le gustaría:

1. Para encriptar sus datos
2. Envíe los datos cifrados a la nube y haga que los servidores de la nube operen con los datos cifrados (sí, lo digo en serio)
3. Enviarle de vuelta los resultados cifrados, que puede descifrar fácilmente

Esto probablemente parece mágico: después de todo, ¿cómo puede alguien operar con datos confusos, crear más datos confusos y luego enviarme algo de basura que se garantiza que descifre la respuesta correcta? Resulta que, dado que la mayoría de los criptosistemas heredan simetrías / operaciones de los objetos matemáticos en los que se basan (grupos, anillos, celosías, campos de números algebraicos), a veces podemos usar estas operaciones sin romper nuestro cifrado.

Antes de dar algunos detalles sobre FHE, veamos un ejemplo. Suponga que le doy una clave pública RSA [math] (N, e) [/ math] y suponga que la clave secreta es [math] d \ equiv e ^ {- 1} \ text {mod} \ phi (N) [/mates]. Entonces dos textos claros [matemática] \ pi_1, \ pi_2 \ in \ Z [/ matemática] se convertirían en textos cifrados [matemática] \ psi_1, \ psi_2 [/ matemática], donde

[math] \ psi_1 = \ pi_1 ^ e \ text {mod} N, \ psi_2 = \ pi_2 ^ e \ text {mod} N [/ math]

Tenga en cuenta que,

[matemática] \ pi_1 \ pi_2 \ text {mod} N = (\ psi_1 ^ d \ text {mod} N) (\ psi_2 ^ d \ text {mod} N) = [/ math]
[matemáticas] (\ psi_1 \ psi_2) ^ d \ text {mod} N [/ matemáticas]
para que el descifrado del producto de dos textos cifrados sea equivalente (mod N) al producto de los dos textos claros. Nuestro objetivo es hacer un sistema que sea tanto multiplicativamente homomórfico (como RSA) como aditivamente homomórfico (que RSA no lo es, como puede ver en la fórmula binomial).

Tenga en cuenta que en este proceso, los servidores en la nube nunca ven sus datos sin procesar . La encriptación totalmente homomórfica hace que esto suceda. El artículo / tesis histórico [0] de Gentry (2009) condujo a algunas revelaciones sorprendentes sobre esquemas de cifrado simples:

• Siempre que un esquema pueda evaluar su propio circuito de descifrado, así como una sola compuerta NAND, se puede iniciar este esquema a un esquema completamente homomórfico
• Las técnicas utilizadas para demostrar las garantías de seguridad post-cuántica resultan útiles para demostrar que existe un esquema de cifrado homomórfico de arranque.
• Incluso esquemas enteros muy simples pueden funcionar

En particular, van Dijk, Gentry, Halevi y Vaikunthan (DGHV) demostraron en [1] que un esquema de criptografía que es más simple que RSA (!!!) es

• Homomórfico para un número prácticamente ilimitado de compuertas aditivas, homomórfico para pequeños números de compuertas multiplicativas
• Bootstrappable
• Tan simple y limpio (en relación con otros sistemas criptográficos, por ejemplo, NTRU) que Bram Cohen lo propuso casualmente en un tablero de mensajes en 2000

Más tarde, Vaikunthan y Brakerski demostraron que se pueden construir esquemas de encriptación homomórficos no arrancables [2] que basan su seguridad en problemas más fuertes y posteriores a la cuantía (por ejemplo, Aprender con errores). Este esquema parece ser más práctico que los esquemas de arranque originales (aunque todavía usa el arranque como ‘una optimización’).

Se puede encontrar un buen resumen no técnico en la revisión técnica del MIT [3]

[0] Tesis doctoral de Craig Gentry
[1] Página en microsoft.com
[2] Página en iacr.org
[3] Cifrado homomórfico – MIT Technology Review

La comprensión de que los algoritmos continuos son útiles (y cruciales) en el diseño de algoritmos altamente eficientes para problemas de optimización discreta en gráficos dispersos.

Por lo que sé, esto se introdujo por primera vez en http://arxiv.org/abs/0803.0988 , que proporcionó (entre otras cosas) un algoritmo para el flujo de costo mínimo que se ejecuta en [matemáticas] \ tilde {O} ( m ^ {3/2}) [/ math] tiempo (m es el número de aristas en el gráfico). Los algoritmos puramente combinatorios para flujos encuentran la `barrera de descomposición del flujo ‘en [math] \ Omega (n ^ 2) [/ math], y hasta la fecha, este es el único algoritmo para el flujo de costo mínimo que se encuentra por debajo de eso.

Avance rápido de 5 años, los desarrollos en esta dirección condujeron a algoritmos para encontrar flujos máximos aproximados (y flujos de múltiples productos) en gráficos no dirigidos en [matemáticas] O (m ^ {1 + \ epsilon}) [/ matemáticas] tiempo ( http: // arxiv.org/abs/1304.2338 , http://arxiv.org/abs/1304.2077 ), y un algoritmo para la coincidencia bipartita máxima que se ejecuta en [matemáticas] \ tilde {O} (m ^ {10/7}) [/ matemáticas] ( http://arxiv.org/abs/1307.2205 ). Este último mejora el mejor tiempo de ejecución anterior para la coincidencia bipartita máxima de [math] O (m ^ {3/2}) [/ math] desde 1971. En este momento, muchos en el área creen que casi todos los algoritmos de optimización de gráficos de libros de texto ( excepto BFS / DFS y el algoritmo de Dijkstra) se reescribirán en unos años.

Otros desarrollos algorítmicos brillantes que vienen a la mente son las aproximaciones y aplicaciones de expansión de gráficos, redondeo de páginas, algoritmos de transmisión y detección de compresión. Sin embargo, solo me burlaré de mí mismo al discutir estos temas.

Algoritmos que evitan la comunicación

Esta es realmente una nueva forma de ver los algoritmos: en lugar de buscar el mejor rendimiento en términos de cálculos, estos algoritmos tienen un modelo de costos que tiene en cuenta la comunicación. La “comunicación” puede ser cualquier cosa, desde mover información a través de grupos hasta simplemente moverla a través de la jerarquía de caché local.

La idea interesante es que en estos días, los costos de comunicación a menudo son al menos tan significativos como los costos de cómputo, por lo que minimizarlos puede tener grandes efectos prácticos. Estas técnicas ya se han utilizado para desarrollar algoritmos mejorados incluso para tareas muy comunes como la multiplicación de matrices y BFS.

Aquí hay un buen powerpoint sobre el tema: http://www.cs.berkeley.edu/~demm …

Estas mismas técnicas también se pueden utilizar para mejorar el uso de energía en lugar del rendimiento.

Del mundo de los algoritmos distribuidos: el enfoque de Google Spanner para implementar un reloj global “casi” sincronizado, llamado TrueTime, y cómo se usa para la sincronización.

Mientras que los enfoques tradicionales de los algoritmos de sincronización en sistemas distribuidos se han diseñado alrededor del enfoque de decir “No confíes en los relojes”. Spanner da la vuelta y usa una combinación de GPS y relojes atómicos para implementar un reloj global confiable con un error dentro del cual se garantiza que obtendrá la hora correcta. Este es un gran enfoque habilitante para construir sistemas distribuidos que requieren muchos menos gastos generales para realizar transacciones distribuidas en comparación con algunos enfoques clásicos.

Creo que es muy innovador por varias razones:

1) Está impulsado por aplicaciones actuales a muy gran escala en lugar de ser teórico (y supongo que mis prejuicios personales de ser un tipo de sistemas probablemente estén mostrando aquí).

2) El pensamiento original combina el hardware con la revisión de los supuestos fundamentales sobre los relojes globales y sobre cómo la gran escala puede venir con garantías de consistencia externa.

3) La idea central se presta a varios casos de uso interesantes.

[1] Publicación de investigación de Google: Spanner

Obviamente estoy sesgado, pero creo que el descubrimiento y el rápido desarrollo del área de redes / algoritmos ahora conocidos como tablas de hash distribuidas (o redes estructuradas punto a punto) probablemente califique.

No sé cuál es la métrica correcta para “brillante”. En este caso, esta clase de algoritmos le permite comunicarse “rápidamente”, es decir, en tiempo O (LogN) a través de redes muy grandes (por ejemplo, billones de nodos). Desde un punto de vista empírico, los DHT han sido bastante influyentes, ya que dominaron las principales conferencias de redes y sistemas durante la mayor parte de 5-6 años a principios de la década de 2000. El conjunto inicial de documentos básicos en este espacio, particularmente aquellos en el primer lote de 4 sistemas (tapiz, pastelería, acorde y CAN), todos tienen más de 10,000 citas en Google Académico.

Durante un tiempo, estos protocolos no se adoptaron en ningún sentido práctico. Luego se usaron para construir bittorrent sin rastreador, luego las ideas / algoritmos centrales se usaron en el almacén de clave / valor NoSQL escalable y eventualmente consistente de Amazon Dynamo (2007), y más recientemente en la plataforma en la nube Azure de Microsoft. También hay variantes de estos algoritmos de “hashing coherente” en almacenes sin SQL como memcached y otros.

Estos son 2 nuevos algoritmos que he escuchado en los últimos tiempos.

Prueba AKS Primality, del Instituto Indio de Tecnología, Kanpur (IITK) en 2002

De acuerdo con Wikipedia ,

AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , polinomial , determinista e incondicional . Los algoritmos anteriores se habían desarrollado durante siglos, pero lograron tres de estas propiedades como máximo, pero no las cuatro.

El nombre del artículo es “PRIMES está en P”.

Mejora en el flujo máximo (algoritmo aproximado) , del Instituto de Tecnología de Massachusetts en 2010

Este artículo trata sobre un nuevo algoritmo aproximado para resolver el problema de flujo máximo en gráficos no dirigidos. Un artículo sobre esto se puede encontrar aquí. De acuerdo con ese artículo,

“Si N es el número de nodos en un gráfico, y L es el número de enlaces entre ellos, entonces la ejecución del algoritmo de flujo máximo anterior más rápido fue proporcional a (N + L) (3/2). La ejecución de el nuevo algoritmo es proporcional a (N + L) (4/3). Para una red como Internet, que tiene cientos de miles de millones de nodos, el nuevo algoritmo podría resolver el problema del flujo máximo cientos de veces más rápido que su predecesor. “

Creo que el año pasado se descubrió que el problema de flujo de red máximo se puede resolver en tiempo [matemático] O (VE) [/ matemático].

Este límite se logró primero para gráficos densos, es decir , [matemática] E \ in \ Omega (V ^ 2) [/ matemática], mediante el algoritmo relabel-to-front, una versión particular del método push-preflow, que se ejecuta en [matemáticas] O (V ^ 3) [/ matemáticas] tiempo. Goldberg y Tarjan publicaron este algoritmo en 1986, y puede encontrarlo en CLRS.

En 1994, King, Rao y Tarjan dieron un algoritmo que se ejecuta en [matemáticas] O \ left (VE \ log (V) / \ log \ left (\ frac {E} {V \ log V} \ right) \ right ) [/ math] tiempo. Esto se reduce a [matemática] O (VE) [/ matemática] para todos los gráficos que no son demasiado escasos, es decir , [matemática] E \ in \ Omega (V ^ {1+ \ epsilon}) [/ matemática]. (Los gráficos con un grado promedio constante o logarítmico aún son un poco escasos).

Finalmente, en 2012, Orlin puso la pieza final en su lugar, encontrando un algoritmo que se ejecuta en [matemáticas] O (VE + E ^ {31/16} \ log ^ 2 V) [/ matemáticas]. Para [matemática] E \ en O (V ^ {16 / 15- \ epsilon}) [/ matemática], es decir, gráficos que son lo suficientemente escasos, esto se reduce a [matemática] O (VE) [/ matemática].

Al combinar el algoritmo de King, Rao y Tarjan, y el algoritmo de Orlin, vemos que el flujo máximo de red se puede resolver en tiempo [matemático] O (VE) [/ matemático]. Creo que eso es asombroso.

Los nuevos métodos IDR para la solución iterativa de sistemas lineales no asimétricos genéricos parecen prometedores:

Enlazar:
IDR

Si bien fue un renacimiento de una técnica conocida en los años 70, solo recientemente se reconoció que tenía un gran potencial para resolver un gran problema en soluciones iterativas: mantener un buen equilibrio entre la velocidad de la solución y el costo de la memoria, un problema que afecta a problemas no simétricos a menos que tenga un problema preacondicionador increíblemente bueno.

Los generadores de números pseudoaleatorios convencionales plantean un problema al software de simulación en paralelo, debido a la dependencia secuencial entre un número aleatorio y su sucesor.

Los generadores de números aleatorios paralelos basados ​​en contadores (de 2011, Salmon et al . “Parallel Random Numbers: Tan fácil como 1,2,3”) hacen que este cuello de botella se evapore para la mayoría de los propósitos prácticos, proporcionando grandes cantidades de pseudoaleatoriedad espectacularmente paralela sin mayor inconvenientes

No se trata tanto de una nueva invención magnífica como de un replanteamiento del problema original, pero esta solución definitivamente me hizo darme una palmada en la frente y recoger la mandíbula inferior del suelo. Hay una implementación coincidente que la acompaña ( http://www.deshawresearch.com/re …) para ofrecer una solución completa a un viejo problema cansado en una placa de plata, creo que es genial.

Miles de millones de transformaciones rápidas de Fourier se ejecutan todos los días. La transformación de Fourier rápida y escasa del MIT mejora la velocidad de las transformaciones de Fourier para una buena variedad de casos prácticos.

La mejora se basa en dar pesos a ciertas frecuencias, procesando solo esas frecuencias importantes (muy ponderadas) de manera eficiente mientras se descarta el resto (sin pérdida significativa de información).

El equipo del MIT no fue el primero en explorar la idea, pero logró obtener un mayor rendimiento de esta técnica, abriendo así las posibilidades de aplicaciones prácticas.

Para más información:
Página en Mit.edu
Una transformación rápida de Fourier más rápida
Transformación rápida de Fourier dispersa (documentos de investigación)

No soy un chico de algoritmos ni una persona de CS para el caso. Pero diría que la detección comprimida es una técnica bastante importante que se desarrolló en los últimos 10 años.

Recuperación estable de la señal de mediciones incompletas e inexactas
http://www-stat.stanford.edu/~ca …

Como una ventaja adicional, Terence Tao (matemático) es uno de los coautores.

http://news.cs.cmu.edu/article.p … En 2010 surgieron algoritmos más rápidos para resolver una clase de sistema de ecuaciones lineales de CMU.

Otro relacionado con la complejidad de la multiplicación de matrices desde finales de 2011: Un avance en el producto de matriz.

Una cosa a tener en cuenta es que los libros de texto son términos relativos. Si bien ninguno de los anteriores es probable que lleguen a los libros de texto de pregrado, ciertamente formarán parte del material de lectura para las clases de posgrado relevantes.

Simplemente cambiando el algoritmo de que los datos se escriben con este avance SSD significa un aumento de velocidad del 300%, un 60% menos de consumo de energía incluso en unidades existentes ya compradas

Esto también debería extender la vida útil del SSD porque reduce la cantidad de escrituras necesarias para llevar sus datos al SSD. Se puede usar en muchos SSD existentes solo con una actualización de firmware.

En las pruebas, las unidades que utilizan la tecnología escribieron datos un 55% menos que las unidades sin ellas y se observaron aumentos de rendimiento de hasta el 300%. Esto podría permitir que los dispositivos de alta gama alcancen fácilmente velocidades de transferencia de 1.5GB / s ya que los modelos actuales alcanzan alrededor de 500MB / s típicamente ; También se usó un 60% menos de energía en las pruebas de laboratorio debido a la falta de escrituras de unidades adicionales.

Vea el enlace a continuación para más detalles …
El avance SSD significa un aumento de velocidad del 300%, un 60% menos de consumo de energía … incluso en unidades viejas – Neowin

La detección comprimida funciona casi como magia, introducida en el siglo XXI si no recuerdo mal, incluso Cleve Moler lo llama reconstrucción mágica 🙂 mira su artículo aquí
El rincón de Cleve – Reconstrucción “mágica”: detección comprimida

Las estructuras de datos “sin bloqueo” y “sin bloqueo” son bastante parecidas a las de 10 años por las que ha preguntado. La literatura académica se remonta aún más, pero su popularidad en los proyectos de software comercial realmente comenzó a despegar en el período 2000-2010.

La idea básica es evitar tomar un candado al modificar árboles, listas, diccionarios y otras estructuras similares, pero sigue siendo seguro para el uso de múltiples subprocesos de la estructura.

Por lo general, esto se hace con instrucciones de CPU de comparación e intercambio (que se garantiza que son atómicas y seguras) en lugar de mecanismos que provocan el bloqueo de otros subprocesos hasta que el subproceso que se está ejecutando cumple alguna condición (por ejemplo, todos los demás esperan hasta el hilo actual ha salido de una sección crítica).

Algoritmos de aproximación realmente buenos para muchos problemas diferentes relacionados con la conectividad en gráficos planos, que son muy similares a las redes de carreteras / infraestructura comunes. Consulte http://cs.brown.edu/~klein/publi …, que proporciona algoritmos de aproximación de tiempo polinomial arbitrariamente buenos para el problema del árbol de Steiner en gráficos planos. Usando una técnica más simple, uno puede obtener algoritmos de aproximación para el problema del vendedor ambulante en gráficos planos. Algunas de las constantes pueden ser difíciles de manejar en este algoritmo. Aquí hay un buen intento de implementar el algoritmo Steiner Tree.

Además, existen algoritmos de aproximación igualmente buenos para problemas de conectividad euclidiana, algunos de los cuales se pueden ver aquí. Para obtener más información sobre estos algoritmos, hay un curso maravilloso en http://courses.csail.mit.edu/6.8 …

LARS (Regresión de ángulo mínimo) es un algoritmo desarrollado por Efron, et. Alabama. en 2003 para resolver la regresión penalizada por L1 (LASSO). Es un algoritmo increíble que proporciona una interpretación intuitiva completamente nueva del problema de optimización que resulta de la regresión penalizada por L1.

En resumen, es básicamente un método que puede seleccionar las variables “correctas” con las que ejecutar un análisis de regresión particular.

http://www.stanford.edu/~hastie/ …

La accesibilidad no dirigida en un gráfico en un espacio de registro inequívoco es bastante reciente, alrededor de 2004. No pude encontrar el documento original, pero está más o menos aquí.
Accesibilidad no dirigida en el espacio de registro

Entonces, no diez años, sino después del siglo XX: Agarwal et al. demostró que la prueba de primalidad está realmente en P! Sin embargo, el exponente polinómico era como 8 mil millones, por lo que a nadie en la industria realmente le importaba. Así que va.