Lugares para reflexionar...
en Washington Square Park
El lugar favorito de Subhash Khot para pensar en la complejidad computacional es el Washington Square Park en la ciudad de Nueva York. Crédito de la imagen: Béatrice de Géa para Quanta Magazine
Por Michael Moyer, Olena Shmahalo y Lucy Reading-Ikkanda, para Quanta Magazinne Agosto 21 de 2017
Como estudiante universitario de la Universidad de Princeton en 2001, Subhash Khot estaba visitando a su familia en la India y pensando en su investigación sobre los límites de la computación cuando se le ocurrió una idea buena, aunque aparentemente modesta. Estaba pensando en un teorema analítico que Johan Håstad, uno de sus mentores, había formulado (y Jean Bourgain lo había demostrado) y cómo podría aplicarse a la "dureza de la aproximación". Pero había un ingrediente que faltaba.
Mientras que la mayoría de los científicos informáticos trabajan para expandir las capacidades de las computadoras, los expertos en complejidad computacional como Khot tratan de determinar qué problemas son imposibles de resolver por los ordenadores en un plazo razonable. Una vez que un problema ha sido clasificado como "duro" de esta manera, la siguiente pregunta natural a preguntarse es acerca de su dureza de aproximación: si una computadora puede encontrar eficientemente una solución aproximada lo suficientemente buena para ponerlo en práctica.
Al pensar en el teorema analítico y en estas preguntas sobre la dureza, Khot se dio cuenta de que el ingrediente que faltaba era un problema existente llamado Unique Games. "Yo planteé que el problema es de hecho computacionalmente difícil, que se convirtió en la Conjetura de Juegos Únicos", dijo Khot a Quanta en un correo electrónico. Encontró que asumiendo que el problema de los Unique Games era difícil hacía mucho más fácil mostrar que otro problema en el que estaba trabajando era también difícil.
"Yo estaba feliz por supuesto y le dije a mi familia que tenía una idea que valía la pena perseguir", dijo Khot. "Ciertamente no pensé que tuviera una gama tan amplia de aplicaciones". Después de regresar a Princeton, se sorprendió al descubrir que su suposición funcionó para varios de sus otros problemas también. Parecía una idea útil, y escribió un artículo que apareció en la primavera siguiente.
En su artículo, Khot encontró conexiones entre su conjetura y una importante dureza del papel de aproximación de Irit Dinur y Shmuel Safra, que estimuló la excitación en el campo. "Creo que estaba en el lugar correcto en el momento adecuado", dijo Khot. En los años siguientes, las conexiones se extendieron a otros grandes problemas, elevando aún más el perfil y la influencia de la conjetura. En 2014, Khot, ahora profesor del Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York, recibió el Premio Rolf Nevanlinna, uno de los máximos honores en informática teórica.
Khot escribió en el pavimento de Washington Square Park algunas de las ideas clave de un enfoque que está desarrollando con Irit Dinur, Guy Kindler, Dor Minzer y Shmuel Safra para probar la Conjetura de Juegos Únicos. Crédito de la imagen: Béatrice de Géa para Quanta Magazine
Como teórico, Khot es capaz de trabajar en cualquier lugar - con sus parientes en la India, en bulliciosos cafés de Nueva York, incluso en salas de cine. Pero su lugar favorito es el Washington Square Park, justo al otro lado de la calle de su oficina de NYU y el departamento de facultad donde vive con su esposa e hijo. "Mi trabajo es principalmente pensando y en su mayor parte, estoy atascado y no estoy progresando", dijo. "Si estuviera en la oficina, me aburriría y me dormitaría".
Pero en el parque, "hay artistas, jugadores de ajedrez, adivinos, bañistas, niños, turistas, coexistiendo con ardillas, palomas, mascotas e incluso un halcón que ha hecho de este barrio su hogar durante varios años", dijo Khot. La proximidad al trabajo, la casa y los restaurantes y cafés cercanos le permiten trabajar, hacer sus tareas, tomar café y cuidar a su hijo. Durante el día, se planta en uno de los bancos sombreados cerca del parque, pero por las tardes prefiere un lugar pintoresco cerca de la fuente de agua.
A pesar de toda la emoción que rodea la conjetura de Khot, la cuestión de si su suposición es verdadera permanece abierta. En estos días, mientras Khot se sienta en silencio en su lugar de pensamiento favorito, rodeado por la energía frenética del parque, está trabajando en dos enfoques para probar la Conjetura de Juegos Únicos, una tarea que no está seguro de que pueda lograrse en su vida.
Corrección: Este artículo fue revisado el 10 de julio de 2017, para indicar correctamente cuándo se encontraron las conexiones entre la conjetura de Khot y el artículo de Irit Dinur y Shmuel Safra.
With a little help from Google Translate for Business
en Washington Square Park
Las grandes ideas tienen una forma de aparecer en entornos inusuales, lejos de una oficina o de una pizarra. Meses atrás, Quanta Magazine se propuso fotografiar a algunos de los científicos y matemáticos más destacados del mundo en sus lugares favoritos para pensar, manipular y crear. Esta serie explora el papel de los espacios acariciados - públicos o privados, de sobra o apretados, dentro o fuera - en la limpieza de un camino a la inspiración.
El lugar favorito de Subhash Khot para pensar en la complejidad computacional es el Washington Square Park en la ciudad de Nueva York. Crédito de la imagen: Béatrice de Géa para Quanta Magazine
Por Michael Moyer, Olena Shmahalo y Lucy Reading-Ikkanda, para Quanta Magazinne Agosto 21 de 2017
Como estudiante universitario de la Universidad de Princeton en 2001, Subhash Khot estaba visitando a su familia en la India y pensando en su investigación sobre los límites de la computación cuando se le ocurrió una idea buena, aunque aparentemente modesta. Estaba pensando en un teorema analítico que Johan Håstad, uno de sus mentores, había formulado (y Jean Bourgain lo había demostrado) y cómo podría aplicarse a la "dureza de la aproximación". Pero había un ingrediente que faltaba.
Mientras que la mayoría de los científicos informáticos trabajan para expandir las capacidades de las computadoras, los expertos en complejidad computacional como Khot tratan de determinar qué problemas son imposibles de resolver por los ordenadores en un plazo razonable. Una vez que un problema ha sido clasificado como "duro" de esta manera, la siguiente pregunta natural a preguntarse es acerca de su dureza de aproximación: si una computadora puede encontrar eficientemente una solución aproximada lo suficientemente buena para ponerlo en práctica.
Al pensar en el teorema analítico y en estas preguntas sobre la dureza, Khot se dio cuenta de que el ingrediente que faltaba era un problema existente llamado Unique Games. "Yo planteé que el problema es de hecho computacionalmente difícil, que se convirtió en la Conjetura de Juegos Únicos", dijo Khot a Quanta en un correo electrónico. Encontró que asumiendo que el problema de los Unique Games era difícil hacía mucho más fácil mostrar que otro problema en el que estaba trabajando era también difícil.
"Yo estaba feliz por supuesto y le dije a mi familia que tenía una idea que valía la pena perseguir", dijo Khot. "Ciertamente no pensé que tuviera una gama tan amplia de aplicaciones". Después de regresar a Princeton, se sorprendió al descubrir que su suposición funcionó para varios de sus otros problemas también. Parecía una idea útil, y escribió un artículo que apareció en la primavera siguiente.
En su artículo, Khot encontró conexiones entre su conjetura y una importante dureza del papel de aproximación de Irit Dinur y Shmuel Safra, que estimuló la excitación en el campo. "Creo que estaba en el lugar correcto en el momento adecuado", dijo Khot. En los años siguientes, las conexiones se extendieron a otros grandes problemas, elevando aún más el perfil y la influencia de la conjetura. En 2014, Khot, ahora profesor del Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York, recibió el Premio Rolf Nevanlinna, uno de los máximos honores en informática teórica.
Khot escribió en el pavimento de Washington Square Park algunas de las ideas clave de un enfoque que está desarrollando con Irit Dinur, Guy Kindler, Dor Minzer y Shmuel Safra para probar la Conjetura de Juegos Únicos. Crédito de la imagen: Béatrice de Géa para Quanta Magazine
Como teórico, Khot es capaz de trabajar en cualquier lugar - con sus parientes en la India, en bulliciosos cafés de Nueva York, incluso en salas de cine. Pero su lugar favorito es el Washington Square Park, justo al otro lado de la calle de su oficina de NYU y el departamento de facultad donde vive con su esposa e hijo. "Mi trabajo es principalmente pensando y en su mayor parte, estoy atascado y no estoy progresando", dijo. "Si estuviera en la oficina, me aburriría y me dormitaría".
Pero en el parque, "hay artistas, jugadores de ajedrez, adivinos, bañistas, niños, turistas, coexistiendo con ardillas, palomas, mascotas e incluso un halcón que ha hecho de este barrio su hogar durante varios años", dijo Khot. La proximidad al trabajo, la casa y los restaurantes y cafés cercanos le permiten trabajar, hacer sus tareas, tomar café y cuidar a su hijo. Durante el día, se planta en uno de los bancos sombreados cerca del parque, pero por las tardes prefiere un lugar pintoresco cerca de la fuente de agua.
A pesar de toda la emoción que rodea la conjetura de Khot, la cuestión de si su suposición es verdadera permanece abierta. En estos días, mientras Khot se sienta en silencio en su lugar de pensamiento favorito, rodeado por la energía frenética del parque, está trabajando en dos enfoques para probar la Conjetura de Juegos Únicos, una tarea que no está seguro de que pueda lograrse en su vida.
Corrección: Este artículo fue revisado el 10 de julio de 2017, para indicar correctamente cuándo se encontraron las conexiones entre la conjetura de Khot y el artículo de Irit Dinur y Shmuel Safra.
With a little help from Google Translate for Business