Pasin Manurangsi: Dimostrare ciò che i computer non possono fare

Nel luglio 2011, la città turistica thailandese di Pattaya ha ospitato la 23ª Olimpiade Internazionale di Informatica, la prima volta che la Thailandia ha ospitato l'evento, e il primo ministro Abhisit Vejjajiva ha inaugurato i giochi in uno dei suoi ultimi atti ufficiali. Tra la squadra di casa c'era un allievo del Bangkok Christian College che è arrivato 14º su 303 concorrenti con 524 punti e ha vinto una seconda medaglia d'oro consecutiva. Ha detto ai giornalisti di essere soddisfatto del 14º posto, che 524 punti erano più di quanto si aspettasse e che sperava che ospitare l'olimpiade avrebbe suscitato più interesse per i computer tra i giovani thailandesi. Quindici anni dopo, Pasin Manurangsi è uno dei ricercatori il cui lavoro consiste nel dire al resto dell'informatica quali problemi sono senza speranza.

L'arco dell'Olimpiade

Il record competitivo di Manurangsi si legge come un esperimento controllato di miglioramento. All'IOI 2009 in Bulgaria ha segnato 516 punti ed è arrivato 67º su 301, portando a casa l'argento. Nel 2010, in Canada, ha segnato 704 punti ed è arrivato 12º su 297, portando a casa l'oro. Nel 2011, in patria, ha vinto di nuovo l'oro mentre la Thailandia vinceva la medaglia d'oro a squadre nella competizione che ospitava per la prima volta. Tre apparizioni, due ori e un argento, e un salto di cinquantacinque posizioni nella classifica mondiale tra il suo primo e il suo secondo tentativo: la traiettoria di qualcuno che ha trattato una sconfitta come un documento di specifica piuttosto che come un verdetto.

MIT e il problema di avvicinarsi abbastanza

Manurangsi ha conseguito sia la laurea che il master presso il Massachusetts Institute of Technology (MIT), dove il suo lavoro di master, supervisionato da Dana Moshkovitz, riguardava algoritmi di approssimazione per giochi di proiezione. Quella scelta di argomento ha dato la direzione a tutto ciò che è seguito. L'approssimazione è il compromesso pragmatico della disciplina: quando un problema non può essere risolto esattamente in un tempo ragionevole, ci si accontenta di una risposta garantita entro un certo fattore dalla migliore. La domanda interessante, a cui Manurangsi è tornato continuamente, è quanto buona possa essere quella garanzia prima di scontrarsi con un muro matematico.

Berkeley: Il paese tra P e NP

Ha completato il dottorato all'Università della California, Berkeley, nel maggio 2019, sotto la co-supervisione di Luca Trevisan e Prasad Raghavendra, con Nikhil Srivastava nel comitato. La tesi era intitolata Approximation and Hardness: Beyond P and NP (Approssimazione e durezza: oltre P e NP), e la sua ambizione è visibile nel titolo. La teoria della complessità classica classifica i problemi in trattabili (P) e notoriamente difficili (NP-completi). La dissertazione di Manurangsi ha deliberatamente cacciato nel terreno che quelle categorie non coprono: problemi che non sono né in P né noti per essere NP-hard, problemi parametrizzati come il k-dominating set, k-clique, k-biclique, rete Steiner diretta e problemi di reticolo, e — la cosa più controintuitiva — problemi che si trovano comodamente all'interno di P, come la coppia più vicina e il prodotto interno massimo, ma che resistono comunque a un'approssimazione veloce. L'abstract afferma che il lavoro risolve due questioni aperte da tempo nella complessità parametrizzata e fornisce i migliori fattori di inapprossimabilità noti per diversi problemi. È una tesi sul tracciare confini, non sull'attraversarli.

Il muro del k-sottografo più denso

Il singolo risultato che lo ha reso famoso riguarda il k-sottografo più denso: dato un network, trovare i k nodi collegati più strettamente. Manurangsi ha dimostrato che, sotto l'ipotesi del tempo esponenziale, nessun algoritmo a tempo polinomiale può ottenere un rapporto di approssimazione migliore di n alla potenza 1/(log log n) elevata a una costante — e che sotto la più forte ipotesi Gap-ETH la barriera si stringe a n^f(n) per qualsiasi funzione f tendente a zero, che è quasi una durezza polinomiale. Crucialmente, la costruzione ha quella che il campo chiama completezza perfetta: distingue grafi che contengono genuinamente una k-clique da grafi in cui ogni k-sottografo è sparso. L'articolo ha vinto il Danny Lewin Best Student Paper Award a STOC 2017, la conferenza di teoria di punta della disciplina.

Google, privacy e divisione equa

Da luglio 2019 Manurangsi è ricercatore scientifico presso Google Research, dove le sue aree elencate sono algoritmi e teoria, intelligenza artificiale e anti-abuso, e dove ha accumulato più di cento pubblicazioni. Il centro di gravità si è spostato dall'inapprossimabilità pura verso la privacy differenziale, la teoria dell'apprendimento e la scelta sociale computazionale — divisione equa, suddivisione del consenso, aggregazione privata dei ranghi, generazione di dati sintetici. Un risultato recente mostra che la suddivisione del consenso fino a O(√(n log n)) beni esiste sempre per n agenti con utilità monotone, migliorando un limite precedente. I premi hanno continuato ad arrivare: Best Paper a WAOA 2021, Best Student Paper ad ALT 2021, un Best Paper e una menzione d'onore per il Best Paper a FORC 2026, oltre al riconoscimento come comitato di programma distinto all'IJCAI nel 2021 e 2023 e lo status di top-reviewer a NeurIPS 2023.

Il viaggio di ritorno

Dal 2022 fa parte dei team di allenatori per le Olimpiadi di Informatica della Thailandia e i suoi campi olimpici di matematica, ed è stato membro delegato ospite per la Thailandia all'IOI 2024. Dal 2023 è anche professore a contratto presso la CMKL University, dove insegna algoritmi, strutture dati e algoritmi per la conservazione della privacy. La pipeline che lo ha prodotto è una che ora aiuta a gestire.

Perché Pasin è chiamato un genio

La qualità cognitiva in questione qui è insolitamente specifica, e non è la velocità pura. Il successo alle Olimpiadi premia la risoluzione rapida e accurata dei problemi sotto pressione; la durezza dell'approssimazione premia quasi l'opposto: la pazienza di costruire un'elaborata riduzione che dimostri che un'intera classe di algoritmi è condannata. Manurangsi è raro per aver fatto entrambe le cose ad alto livello, e la tesi di Berkeley ne è la prova: rivendica un territorio che la maggior parte dei ricercatori evita proprio perché i risultati negativi sono più difficili da pubblicare e più difficili da ottenere correttamente. Un singolo errore logico in una riduzione invalida tutto.

Il controargomento onesto è sostanziale. Nulla nel registro disponibile — la sua homepage, il profilo Google Research, la dissertazione o la copertura giornalistica thailandese contemporanea — usa la parola "genio" nei suoi confronti. I suoi riconoscimenti sono premi dei colleghi dei comitati di conferenza, che riconoscono il miglior articolo in una stanza, non una mente per le epoche. L'informatica teorica è anche implacabilmente collaborativa; i suoi oltre cento articoli sono il prodotto di co-autoria, seminari e un gruppo di Berkeley guidato da due dei teorici della complessità più forti del campo. Il suo record all'IOI, sebbene eccellente, include un 67º posto. Ciò che può essere detto senza esagerazioni è più stretto e più interessante: è un professionista di primo livello in uno degli angoli tecnicamente più impegnativi della matematica, e il suo risultato determinante ha chiuso una questione che era rimasta aperta per anni. Questo non è lo stesso che essere un genio, e lui non ha mai affermato che lo fosse.

Prospettive

La carriera di Manurangsi ha una forma insolita per un teorico: le prove di impossibilità sono arrivate per prime, il lavoro sulla privacy applicata per secondo. Il passaggio alla privacy differenziale e alla divisione equa suggerisce qualcuno che, dopo aver stabilito dove sono i muri, ora preferirebbe costruire al loro interno. L'allenamento per le olimpiadi thailandesi potrebbe rivelarsi l'eredità più duratura: un paese che ha ospitato l'IOI una volta, e ora fa crescere le persone che la vincono.