Pasin Manurangsi: Demostrando lo que las computadoras no pueden hacer

En julio de 2011, la ciudad turística tailandesa de Pattaya organizó la 23ª Olimpiada Internacional de Informática, la primera vez que Tailandia albergaba el evento, y el primer ministro Abhisit Vejjajiva inauguró los juegos en uno de sus últimos actos oficiales. Entre el equipo local se encontraba un alumno del Bangkok Christian College que terminó 14º de 303 competidores con 524 puntos y obtuvo una segunda medalla de oro consecutiva. Dijo a los periodistas que estaba satisfecho con el 14º puesto, que 524 puntos eran más de lo que esperaba y que esperaba que organizar la olimpiada despertara más interés por la informática entre los jóvenes tailandeses. Quince años después, Pasin Manurangsi es uno de los investigadores cuyo trabajo consiste en decir al resto de la informática qué problemas son desesperados.

El arco de la Olimpiada

El historial competitivo de Manurangsi se lee como un experimento controlado de mejora. En la IOI de 2009 en Bulgaria obtuvo 516 puntos y terminó 67º de 301, llevándose la plata. En 2010, en Canadá, obtuvo 704 puntos y terminó 12º de 297, llevándose el oro. En 2011, en su país, volvió a conseguir el oro, ya que Tailandia ganó la medalla de oro por equipos en la competición que organizaba por primera vez. Tres participaciones, dos oros y una plata, y un salto de cincuenta y cinco puestos en la clasificación mundial entre su primer y segundo intento: la trayectoria de alguien que trató una derrota como un documento de especificación en lugar de un veredicto.

MIT y el problema de acercarse lo suficiente

Manurangsi cursó su licenciatura y su máster en el Instituto Tecnológico de Massachusetts (MIT), donde su trabajo de máster, supervisado por Dana Moshkovitz, se centró en algoritmos de aproximación para juegos de proyección. Esa elección de tema marcó la dirección de todo lo que siguió. La aproximación es el compromiso pragmático de la disciplina: cuando un problema no puede resolverse exactamente en un tiempo razonable, te conformas con una respuesta garantizada dentro de algún factor de la mejor. La pregunta interesante, a la que Manurangsi volvía constantemente, es lo buena que puede llegar a ser esa garantía antes de chocar contra un muro matemático.

Berkeley: La tierra entre P y NP

Completó su doctorado en la Universidad de California, Berkeley, en mayo de 2019, codirigido por Luca Trevisan y Prasad Raghavendra, con Nikhil Srivastava en el comité. La tesis se tituló Approximation and Hardness: Beyond P and NP (Aproximación y dureza: más allá de P y NP), y su ambición es visible en el título. La teoría de la complejidad clásica clasifica los problemas en tratables (P) y notoriamente difíciles (NP-completos). La disertación de Manurangsi exploró deliberadamente el terreno que esas categorías no cubren: problemas que no están en P ni se sabe que sean NP-duros, problemas parametrizados como el conjunto k-dominante, k-clique, k-biclique, red Steiner dirigida y problemas de retículos, y, lo que es más contraintuitivo, problemas que se sitúan cómodamente dentro de P, como el par más cercano y el producto interior máximo, pero que se resisten a una aproximación rápida de todos modos. El resumen afirma que el trabajo resuelve dos preguntas abiertas desde hace mucho tiempo en la complejidad parametrizada y ofrece los mejores factores de inaproximabilidad conocidos para varios problemas. Es una tesis sobre trazar fronteras, no sobre cruzarlas.

El muro del k-subgrafo más denso

El único resultado que le hizo famoso se refiere al k-subgrafo más denso: dado un grafo, encontrar los k nodos empaquetados más estrechamente con conexiones. Manurangsi demostró que, bajo la hipótesis del tiempo exponencial, ningún algoritmo de tiempo polinómico puede lograr una relación de aproximación mejor que n a la potencia 1/(log log n) elevada a una constante, y que bajo la suposición más fuerte Gap-ETH, la barrera se ajusta a n^f(n) para cualquier función f que tienda a cero, lo que es casi una dureza polinómica. Fundamentalmente, la construcción tiene lo que el campo llama completitud perfecta: distingue grafos que contienen genuinamente un k-clique de aquellos donde cada k-subgrafo es escaso. El artículo ganó el premio Danny Lewin al mejor artículo estudiantil en STOC 2017, la principal conferencia de teoría de la disciplina.

Google, privacidad y división justa

Desde julio de 2019, Manurangsi ha sido científico investigador en Google Research, donde sus áreas enumeradas son algoritmos y teoría, inteligencia de máquinas y anti-abuso, y donde ha acumulado más de cien publicaciones. El centro de gravedad se ha desplazado de la inaproximabilidad pura hacia la privacidad diferencial, la teoría del aprendizaje y la elección social computacional: división justa, división de consenso, agregación de rangos privados, generación de datos sintéticos. Un resultado reciente muestra que siempre existe una división de consenso hasta O(√(n log n)) bienes para n agentes con utilidades monótonas, mejorando un límite anterior. Los premios han seguido llegando: mejor artículo en WAOA 2021, mejor artículo estudiantil en ALT 2021, un mejor artículo y una mención honorífica a mejor artículo en FORC 2026, además de un reconocimiento distinguido del comité de programa en IJCAI en 2021 y 2023 y el estatus de revisor superior en NeurIPS 2023.

El viaje de regreso

Desde 2022 forma parte de los equipos de entrenamiento para la Olimpiada de Informática de Tailandia y sus campamentos de olimpiadas matemáticas, y ejerció como miembro invitado de la delegación de Tailandia en la IOI de 2024. Desde 2023 también ha sido profesor adjunto en la Universidad CMKL, enseñando algoritmos, estructuras de datos y algoritmos que preservan la privacidad. La cadena que lo produjo es una que ahora ayuda a dirigir.

Por qué Pasin es llamado un genio

La cualidad cognitiva en cuestión aquí es inusualmente específica, y no es la velocidad bruta. El éxito en las olimpiadas recompensa la resolución rápida y precisa de problemas bajo un reloj; la dureza de la aproximación recompensa casi lo contrario: la paciencia para construir una reducción elaborada que pruebe que toda una clase de algoritmos está condenada. Manurangsi es raro por haber hecho ambas cosas a un alto nivel, y la tesis de Berkeley es la prueba: marca un territorio que la mayoría de los investigadores evitan precisamente porque los resultados negativos son más difíciles de publicar y más difíciles de acertar. Un solo error lógico en una reducción invalida todo.

El contraargumento honesto es sustancial. Nada en el registro disponible —su propia página web, perfil de Google Research, disertación o la cobertura de prensa tailandesa contemporánea— usa la palabra "genio" sobre él. Sus honores son premios de pares de comités de conferencias, que reconocen el mejor artículo en una sala, no una mente para las edades. La informática teórica también es implacablemente colaborativa; sus más de cien artículos son producto de la coautoría, seminarios y un grupo de Berkeley liderado por dos de los teóricos de la complejidad más fuertes del campo. Su historial en la IOI, aunque excelente, incluye un 67º puesto. Lo que se puede decir sin inflación es más estrecho y más interesante: es un profesional de primer nivel en uno de los rincones técnicamente más exigentes de las matemáticas, y su resultado definitorio cerró una pregunta que había estado abierta durante años. Eso no es lo mismo que ser un genio, y él nunca ha afirmado que lo sea.

Perspectiva

La carrera de Manurangsi tiene una forma inusual para un teórico: las pruebas de imposibilidad llegaron primero, el trabajo de privacidad aplicada en segundo lugar. El paso a la privacidad diferencial y la división justa sugiere a alguien que, tras establecer dónde están los muros, preferiría ahora construir dentro de ellos. El entrenamiento para la olimpiada tailandesa puede resultar el legado más duradero: un país que organizó la IOI una vez y ahora cultiva a las personas que la ganan.