Pasin Manurangsi: Beweisen, was Computer nicht können

Im Juli 2011 veranstaltete die thailändische Touristenstadt Pattaya die 23. Internationale Informatik-Olympiade, das erste Mal, dass Thailand das Ereignis ausrichtete, und Premierminister Abhisit Vejjajiva eröffnete die Spiele in einem seiner letzten offiziellen Akte. Unter dem heimischen Team befand sich ein Schüler des Bangkok Christian College, der mit 524 Punkten den 14. von 303 Wettbewerbern belegte und eine zweite Goldmedaille in Folge holte. Er erzählte Reportern, er sei mit dem 14. Platz zufrieden, dass 524 Punkte mehr seien, als er erwartet hatte, und dass er hoffe, die Ausrichtung der Olympiade würde bei thailändischen Jugendlichen mehr Interesse an Computern wecken. Fünfzehn Jahre später ist Pasin Manurangsi einer der Forscher, deren Job es ist, dem Rest der Informatik zu sagen, welche Probleme hoffnungslos sind.

Der Olympia-Bogen

Manurangsis Wettbewerbsbilanz liest sich wie ein kontrolliertes Experiment zur Verbesserung. Bei der IOI 2009 in Bulgarien erzielte er 516 Punkte und belegte den 67. von 301 Plätzen, wobei er Silber holte. Im Jahr 2010 erzielte er in Kanada 704 Punkte und belegte den 12. von 297 Plätzen, wobei er Gold holte. 2011, auf heimischem Boden, holte er erneut Gold, als Thailand bei dem Wettbewerb, den es zum ersten Mal ausrichtete, die Mannschaftsgoldmedaille gewann. Drei Auftritte, zwei Goldmedaillen und eine Silbermedaille sowie ein Sprung von fünfundfünfzig Plätzen in der Weltrangliste zwischen seinem ersten und seinem zweiten Versuch: die Laufbahn von jemandem, der einen Verlust eher als Spezifikationsdokument denn als Urteil behandelte.

MIT und das Problem, nahe genug heranzukommen

Manurangsi absolvierte sowohl seinen Bachelor als auch seinen Master am Massachusetts Institute of Technology (MIT), wo seine Masterarbeit, betreut von Dana Moshkovitz, Approximationsalgorithmen für Projektionsspiele betraf. Diese Themenwahl bestimmte die Richtung von allem, was folgte. Approximation ist der pragmatische Kompromiss der Disziplin: Wenn ein Problem nicht exakt in angemessener Zeit gelöst werden kann, gibt man sich mit einer Antwort zufrieden, die innerhalb eines bestimmten Faktors der besten garantiert ist. Die interessante Frage, zu der Manurangsi immer wieder zurückkehrte, ist, wie gut diese Garantie sein kann, bevor sie gegen eine mathematische Mauer stößt.

Berkeley: Das Land zwischen P und NP

Er schloss seine Promotion an der University of California, Berkeley, im Mai 2019 ab, co-betreut von Luca Trevisan und Prasad Raghavendra, mit Nikhil Srivastava im Komitee. Die Dissertation trug den Titel Approximation and Hardness: Beyond P and NP (Approximation und Härte: Jenseits von P und NP), und ihr Ehrgeiz ist im Titel sichtbar. Die klassische Komplexitätstheorie sortiert Probleme in die lösbaren (P) und die notorisch schweren (NP-vollständig) ein. Manurangsis Dissertation suchte bewusst in dem Terrain, das diese Kategorien nicht abdecken: Probleme, die weder in P sind noch als NP-schwer bekannt sind, parametrisierte Probleme wie k-dominierende Menge, k-Clique, k-Biclique, gerichtetes Steiner-Netzwerk und Gitterprobleme, und — am kontraintuitivsten — Probleme, die bequem innerhalb von P sitzen, wie das nächste Paar und das maximale innere Produkt, die sich aber trotzdem einer schnellen Approximation widersetzen. Das Abstract behauptet, dass die Arbeit zwei langjährige offene Fragen der parametrisierten Komplexität löst und die besten bekannten Inapproximierbarkeitsfaktoren für mehrere Probleme liefert. Es ist eine Dissertation über das Ziehen von Grenzen, nicht über deren Überschreiten.

Die Mauer des dichtesten k-Teilgraphen

Das einzelne Ergebnis, das seinen Namen bekannt machte, betrifft den dichtesten k-Teilgraphen: Gegeben sei ein Netzwerk, finde die k Knoten, die am engsten mit Verbindungen gepackt sind. Manurangsi bewies, dass unter der Exponentialzeit-Hypothese kein Polynomialzeit-Algorithmus ein Approximationsverhältnis besser als n hoch 1/(log log n) hoch eine Konstante erreichen kann — und dass unter der stärkeren Gap-ETH-Annahme die Barriere auf n^f(n) für jede Funktion f, die gegen Null tendiert, schrumpft, was fast polynomiale Härte ist. Entscheidend ist, dass die Konstruktion das hat, was das Fachgebiet perfekte Vollständigkeit nennt: Sie unterscheidet Graphen, die tatsächlich eine k-Clique enthalten, von Graphen, in denen jeder k-Teilgraph spärlich ist. Die Arbeit gewann den Danny Lewin Best Student Paper Award auf der STOC 2017, der wichtigsten Theorie-Konferenz der Disziplin.

Google, Privatsphäre und faire Teilung

Seit Juli 2019 ist Manurangsi Forschungswissenschaftler bei Google Research, wo seine aufgeführten Bereiche Algorithmen und Theorie, Maschinenintelligenz und Anti-Missbrauch sind und wo er mehr als hundert Publikationen gesammelt hat. Der Schwerpunkt hat sich von reiner Inapproximierbarkeit hin zu differenzieller Privatsphäre, Lerntheorie und computationaler Sozialwahl verschoben — faire Teilung, Konsenshalbierung, private Rangaggregation, synthetische Datengenerierung. Ein aktuelles Ergebnis zeigt, dass eine Konsenshalbierung bis zu O(√(n log n)) Gütern für n Agenten mit monotonen Nutzen immer existiert, was eine frühere Grenze verbessert. Die Auszeichnungen kamen weiterhin an: Best Paper auf der WAOA 2021, Best Student Paper auf der ALT 2021, ein Best Paper und eine Best Paper Honorable Mention auf der FORC 2026, dazu Anerkennung des Programmkomitees auf der IJCAI in 2021 und 2023 sowie der Status als Top-Reviewer bei der NeurIPS 2023.

Die Rückreise

Seit 2022 ist er Teil der Coaching-Teams für Thailands Informatik-Olympiade und deren mathematische Olympiade-Camps, und er diente als Gastdelegationsmitglied für Thailand bei der IOI 2024. Seit 2023 ist er auch außerordentlicher Professor an der CMKL University und lehrt Algorithmen, Datenstrukturen und datenschutzfreundliche Algorithmen. Die Pipeline, die ihn hervorgebracht hat, ist eine, die er jetzt mitbetreibt.

Warum Pasin ein Genie genannt wird

Die hier betroffene kognitive Qualität ist ungewöhnlich spezifisch, und es ist nicht rohe Geschwindigkeit. Olympia-Erfolg belohnt schnelles, genaues Problemlösen unter Zeitdruck; Härte der Approximation belohnt fast das Gegenteil — die Geduld, eine aufwendige Reduktion aufzubauen, die beweist, dass eine ganze Klasse von Algorithmen zum Scheitern verurteilt ist. Manurangsi ist selten darin, beides auf hohem Niveau getan zu haben, und die Berkeley-Dissertation ist der Beweis: Sie steckt Territorium ab, das die meisten Forscher meiden, gerade weil negative Ergebnisse schwerer zu veröffentlichen und schwerer richtig zu bekommen sind. Ein einziger logischer Ausrutscher in einer Reduktion entwertet alles.

Der ehrliche Gegenpunkt ist substanziell. Nichts in der zugänglichen Aufzeichnung — seine eigene Homepage, das Google Research-Profil, die Dissertation oder die zeitgenössische thailändische Presseberichterstattung — verwendet das Wort "Genie" für ihn. Seine Auszeichnungen sind Peer-Awards von Konferenzkomitees, die das beste Paper im Raum anerkennen, nicht einen Geist für die Ewigkeit. Theoretische Informatik ist auch unerbittlich kollaborativ; seine über hundert Paper sind das Produkt von Co-Autorenschaft, Seminaren und einer Berkeley-Gruppe, die von zwei der stärksten Komplexitätstheoretiker des Feldes geleitet wird. Sein IOI-Rekord, obwohl exzellent, beinhaltet einen 67. Platz. Was ohne Aufblähung gesagt werden kann, ist enger und interessanter: Er ist ein erstklassiger Profi in einer der technisch anspruchsvollsten Ecken der Mathematik, und sein definierendes Ergebnis schloss eine Frage, die jahrelang offen war. Das ist nicht dasselbe wie ein Genie, und er hat nie behauptet, dass es das sei.

Ausblick

Manurangsis Karriere hat eine ungewöhnliche Form für einen Theoretiker: die Unmöglichkeitsbeweise kamen zuerst, die Arbeit zur angewandten Privatsphäre zweitens. Der Wechsel zur differenziellen Privatsphäre und zur fairen Teilung deutet auf jemanden hin, der, nachdem er festgestellt hat, wo die Mauern sind, jetzt lieber innerhalb dieser Mauern bauen möchte. Das thailändische Olympiade-Coaching könnte sich als das dauerhaftere Vermächtnis erweisen — ein Land, das die IOI einmal ausrichtete und nun die Leute heranwachsen lässt, die sie gewinnen.