Nati Linial - Nati Linial
Nathan (Nati) Linial (nacido en 1953 en Haifa , Israel ) es un matemático e informático israelí , profesor de la Escuela de Informática e Ingeniería Rachel and Selim Benin de la Universidad Hebrea de Jerusalén y un investigador muy citado del ISI .
Linial hizo sus estudios de pregrado en el Technion y recibió su doctorado en 1978 de la Universidad Hebrea bajo la supervisión de Micha Perles. Fue investigador de posgrado en la Universidad de California, Los Ángeles antes de regresar a la Universidad Hebrea como miembro de la facultad.
En 2012 se convirtió en miembro de la American Mathematical Society . En 2019 ganó el premio FOCS Test of Time por el artículo " Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje ", en coautoría con Yishay Mansour y Noam Nisan.
Publicaciones Seleccionadas
- Linial, Nati (1992), "Localidad en algoritmos de grafos distribuidos", SIAM J. Comput. , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137 / 0221015. El artículo ganó el premio Dijkstra 2013 . En palabras del comité del premio: "Este artículo ha tenido un gran impacto en los algoritmos de transmisión de mensajes distribuidos. Se centró en la noción de localidad en la computación distribuida y planteó preguntas interesantes sobre el nivel de localidad de varios problemas distribuidos, en términos de su complejidad temporal en diferentes clases de redes. Con ese objetivo, en este artículo, Linial desarrolló un modelo particularmente adecuado para estudiar la localidad, que ignora los tamaños de los mensajes, la asincronía y las fallas. Este modelo limpio permitió a los investigadores aislar los efectos de la localidad y estudiar los roles de las distancias y vecindarios, como nociones teóricas de grafos, y sus interrelaciones con problemas algorítmicos y teóricos de la complejidad en la computación distribuida ".
- Borodin, Allan ; Linial, Nathan; Saks, Michael E. (1992), "Un algoritmo en línea óptimo para el sistema de tareas métricas", J. ACM , 39 (4): 745–763, doi : 10.1145 / 146585.146588 , S2CID 18783826. Este artículo sobre análisis competitivo de algoritmos en línea estudia los sistemas de tareas métricas , un modelo muy general de tareas en el que las decisiones sobre cómo atender una secuencia de solicitudes deben tomarse sin conocimiento de solicitudes futuras. Introduce el modelo del sistema de tareas métricas, describe cómo usarlo para modelar varios problemas de programación y desarrolla un algoritmo que en muchas situaciones se puede demostrar que funciona de manera óptima.
- Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993), "Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje", J. ACM , 40 (3): 607–620, doi : 10.1145 / 174130.174138 , S2CID 16978276. Al realizar un análisis armónico en funciones en la clase de complejidad AC 0 (una clase que representa problemas computacionales altamente paralelizables ), Linial y sus coautores muestran que estas funciones se comportan mal como generadores de números pseudoaleatorios , se pueden aproximar bien mediante polinomios y se pueden aprender eficientemente mediante sistemas de aprendizaje automático .
- Linial, Nathan; Londres, Eran; Rabinovich, Yuri (1995), "La geometría de los gráficos y algunas de sus aplicaciones algorítmicas", Combinatorica , 15 (2): 215–245, doi : 10.1007 / BF01200757 , S2CID 5071936. El artículo más citado de Linial según el académico de Google , este artículo explora las conexiones entre los problemas de la teoría de los gráficos, como el problema del flujo de múltiples productos básicos, y las incrustaciones de baja distorsión de espacios métricos en espacios de baja dimensión, como los dados por el lema de Johnson-Lindenstrauss. .
- Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Gráficos expansores y sus aplicaciones", Boletín de la American Mathematical Society , 43 (4): 439–561, doi : 10.1090 / S0273-0979-06-01126-8 , MR 2247919. En 2008, Linial y sus coautores ganaron el premio Levi L. Conant de la American Mathematical Society a la mejor exposición matemática para este artículo, una encuesta sobre gráficos expansores .