Algunos de los jóvenes investigadores prometedores en el campo de la informática teórica (en orden aleatorio) son:
00. Nitin Saxena -IIT Kanpur (Galardonado con el Clay Research Award ’02, Fulkerson Prize ’06, Godel Prize ’06)
Él junto con sus colaboradores Manindra Agrawal y Neeraj Kayal crearon la prueba de primalidad AKS en 2002. Hizo su B Tech en CSE de IIT-K durante 1998-2002 y luego continuó su doctorado allí desde 2002-2006. Se unió al IIT-K CSE Dept. como facultad / investigador en 2013. Está ampliamente interesado en la teoría de la complejidad computacional, álgebra, geometría y teoría de números.
01. David P. Woodruff – IBM (Beneficiario del Premio Presburger ’14)
Ha realizado importantes contribuciones a la teoría de los flujos de datos, tanto creando nuevos algoritmos como demostrando que ciertos algoritmos no pueden existir. Su trabajo tiene un impacto en otros campos, incluida la detección comprimida, el aprendizaje automático y el álgebra lineal numérica. En el área de flujos de datos, resolvió el problema de elementos distintos, optimizando simultáneamente la cantidad de memoria utilizada, el tiempo necesario para procesar cada entidad nueva y el tiempo necesario para informar una estimación del número de elementos distintos en el flujo. En el área del aprendizaje automático, utilizó sus resultados anteriores en flujos de datos para diseñar algoritmos sublineales para la clasificación lineal y los problemas mínimos de la bola envolvente. En álgebra lineal numérica, desarrolló los primeros algoritmos para aproximación y regresión de bajo rango que se ejecutan en tiempo proporcional al número de entradas distintas de cero de la matriz de entrada. Su trabajo también resultó en 17 patentes relacionadas con flujos de datos y sus aplicaciones. [1]
- ¿Cuál es el algoritmo más rápido para encontrar el número más grande en una matriz sin clasificar con múltiples procesadores?
- ¿Cómo resolverías (2 ^ 2 ^ a mod b)?
- ¿Cómo se puede determinar la coincidencia más cercana de un vector dado entre un conjunto de vectores si el origen de los vectores también es importante?
- Dada una instancia tautológica de DNF-SAT, ¿se conserva la tautología después de agregar un nuevo literal [math] v [/ math] o [math] \ bar {v} [/ math] a una cláusula que se sabe que está en PTIME?
- ¿Qué es la skolemización?
10. Jon Kleinberg (Ganador del Premio Nevanlinna ’06 por la Unión Internacional de Matemáticas, Premio Harvey ’13)
Es mejor conocido por su trabajo en redes y particularmente por su algoritmo HITS. HITS es un algoritmo para la búsqueda web que se basa en los métodos basados en vectores propios utilizados en algoritmos y sirvió como modelo a escala completa para PageRank al reconocer que las páginas web o sitios deben considerarse importantes no solo si están vinculados por muchos otros (como en PageRank), pero también si se vinculan a muchos otros. Los propios motores de búsqueda son ejemplos de sitios que son importantes porque enlazan con muchos otros. Kleinberg se dio cuenta de que esta generalización implica dos clases diferentes de páginas web importantes, a las que llamó “centros” y “autoridades”. El algoritmo HITS es un algoritmo para identificar automáticamente los principales centros y autoridades en una red de páginas con hipervínculos.
También es conocido por su trabajo en aspectos algorítmicos del experimento del mundo pequeño. Fue uno de los primeros en darse cuenta de que el famoso experimento de paso de letras de “seis grados” de Stanley Milgram implicaba no solo que hay caminos cortos entre los individuos en las redes sociales, sino también que las personas parecen ser buenas para encontrar esos caminos, una observación aparentemente simple. eso resulta tener profundas implicaciones para la estructura de las redes en cuestión. [2]
11. Rahul Santhanam
Coautor del artículo galardonado del Premio Nerode 2014, “Incompatibilidad de la compresión de instancias y PCP sucintos para NP”, en el área de algoritmos multivariados.
Los intereses de investigación están en algoritmos y complejidad, con énfasis en la teoría de la complejidad y sus aplicaciones a la criptografía, la teoría de juegos y la teoría del aprendizaje. [3]
100. Danny Hermelin
Coautor del trabajo ganador del premio Nerode Prize 2014, “Sobre problemas sin núcleos polinomiales”, en el área de algoritmos multivariados.
Los intereses de investigación son Algoritmos de gráficos, Complejidad parametrizada, Algoritmos de aproximación, Emparejamiento de patrones combinatorios. [3]
101. Venkatesan Guruswami (Ganador del Premio Presburger ’12)
110. Erik Demaine (Ganador del Premio Presburger ’13)
111. Patricia Bouyer (Ganadora del Premio Presburger ’11)
1000. Mikołaj Bojańczyk’s (Ganador del Premio Presburger ’10)
Fuentes:
[1] Premio Presburger 2014
[2] Jon Kleinberg
[3] Asociación Europea de Informática Teórica
[4] Premio Presburger
[5] Respuesta del usuario de Quora a ¿Cuáles son algunos de los mejores proyectos realizados por los estudiantes de IIT en el ámbito académico?
