Pasin Manurangsi: Proving What Computers Cannot Do
In July 2011 the Thai resort city of Pattaya staged the 23rd International Olympiad in Informatics, the first time Thailand had ever hosted the event, and Prime Minister Abhisit Vejjajiva opened the games in one of his final official acts. Among the home team was a pupil from Bangkok Christian College who finished 14th out of 303 competitors with 524 points and collected a second consecutive gold medal. He told reporters he was pleased with 14th, that 524 points was more than he had expected, and that he hoped hosting the olympiad would trigger more interest in computers among Thai youths. Fifteen years on, Pasin Manurangsi is one of the researchers whose job is to tell the rest of computer science which problems are hopeless.
The Olympiad Arc
Manurangsi's competitive record reads like a controlled experiment in improvement. At the 2009 IOI in Bulgaria he scored 516 points and finished 67th of 301, taking silver. In 2010, in Canada, he scored 704 and finished 12th of 297, taking gold. In 2011, on home soil, he took gold again as Thailand won the team gold medal at the competition it was hosting for the first time. Three appearances, two golds and a silver, and a jump of fifty-five places in the world ranking between his first and second attempts: the trajectory of somebody who treated a loss as a specification document rather than a verdict.
MIT, and the Problem of Getting Close Enough
Manurangsi took both his bachelor's and master's degrees at the Massachusetts Institute of Technology, where his master's work, supervised by Dana Moshkovitz, concerned approximation algorithms for projection games. That choice of topic set the direction of everything that followed. Approximation is the discipline's pragmatic compromise: when a problem cannot be solved exactly in reasonable time, you settle for an answer guaranteed to be within some factor of the best one. The interesting question, and the one Manurangsi kept returning to, is how good that guarantee can possibly be before it collides with a mathematical wall.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Berkeley: The Country Between P and NP
He completed his doctorate at the University of California, Berkeley in May 2019, co-supervised by Luca Trevisan and Prasad Raghavendra, with Nikhil Srivastava on the committee. The thesis was titled *Approximation and Hardness: Beyond P and NP*, and its ambition is visible in the title. Classical complexity theory sorts problems into the tractable (P) and the notoriously hard (NP-complete). Manurangsi's dissertation deliberately went hunting in the terrain those categories do not cover: problems that are neither in P nor known to be NP-hard, parameterized problems such as k-dominating set, k-clique, k-biclique, directed Steiner network and lattice problems, and — most counter-intuitively — problems that sit comfortably inside P, like closest pair and maximum inner product, but which resist fast approximation anyway. The abstract claims the work resolves two long-standing open questions in parameterized complexity and delivers the best known inapproximability factors for several problems. It is a thesis about drawing borders, not crossing them.
The Densest k-Subgraph Wall
The single result that made his name concerns Densest k-Subgraph: given a network, find the k nodes packed most tightly with connections. Manurangsi proved that under the exponential time hypothesis, no polynomial-time algorithm can achieve an approximation ratio better than n to the power 1/(log log n) raised to a constant — and that under the stronger Gap-ETH assumption the barrier tightens to n^f(n) for any function f tending to zero, which is very nearly polynomial hardness. Crucially the construction has what the field calls perfect completeness: it distinguishes graphs that genuinely contain a k-clique from graphs where every k-subgraph is sparse. The paper won the Danny Lewin Best Student Paper Award at STOC 2017, the discipline's flagship theory conference.
Google, Privacy and Fair Division
Since July 2019 Manurangsi has been a research scientist at Google Research, where his listed areas are algorithms and theory, machine intelligence, and anti-abuse, and where he has accumulated more than a hundred publications. The centre of gravity has shifted from pure inapproximability toward differential privacy, learning theory and computational social choice — fair division, consensus halving, private rank aggregation, synthetic data generation. One recent result shows that consensus halving up to O(√(n log n)) goods always exists for n agents with monotone utilities, improving a previous bound. The awards have kept arriving: Best Paper at WAOA 2021, Best Student Paper at ALT 2021, a Best Paper and a Best Paper Honorable Mention at FORC 2026, plus distinguished programme committee recognition at IJCAI in 2021 and 2023 and top-reviewer status at NeurIPS 2023.
The Return Trip
Since 2022 he has been part of the coaching teams for Thailand's Olympiad in Informatics and its mathematical olympiad camps, and he served as a guest delegation member for Thailand at the 2024 IOI. Since 2023 he has also been adjunct faculty at CMKL University, teaching algorithms, data structures and privacy-preserving algorithms. The pipeline that produced him is one he now helps run.
Why Pasin Is Called a Genius
The cognitive quality at issue here is unusually specific, and it is not raw speed. Olympiad success rewards fast, accurate problem-solving under a clock; hardness of approximation rewards almost the opposite — the patience to construct an elaborate reduction proving that a whole class of algorithms is doomed. Manurangsi is rare in having done both at a high level, and the Berkeley thesis is the evidence: it stakes out territory that most researchers avoid precisely because negative results are harder to get published and harder to get right. A single logical slip in a reduction invalidates everything.
The honest counter-case is substantial. Nothing in the sourced record — his own homepage, Google Research profile, dissertation, or the contemporaneous Thai press coverage — uses the word "genius" about him. His honours are peer awards from conference committees, which recognise the best paper in a room, not a mind for the ages. Theoretical computer science is also relentlessly collaborative; his hundred-plus papers are the product of co-authorship, seminars and a Berkeley group led by two of the field's strongest complexity theorists. His IOI record, while excellent, includes a 67th-place finish. What can be said without inflation is narrower and more interesting: he is a first-rate professional in one of the most technically demanding corners of mathematics, and his defining result closed a question that had been open for years. That is not the same as genius, and he has never claimed it is.
Outlook
Manurangsi's career has an unusual shape for a theorist: the impossibility proofs came first, the applied privacy work second. The move to differential privacy and fair division suggests someone who, having established where the walls are, would now rather build inside them. The Thai olympiad coaching may prove the more durable legacy — a country that hosted the IOI once, and now grows the people who win it.
