Pasin Manurangsi: Provando o que os computadores não podem fazer

Em julho de 2011, a cidade turística tailandesa de Pattaya sediou a 23ª Olimpíada Internacional de Informática, a primeira vez que a Tailândia organizou o evento, e o primeiro-ministro Abhisit Vejjajiva abriu os jogos num dos seus últimos atos oficiais. Entre a equipa da casa estava um aluno do Bangkok Christian College que terminou em 14º lugar entre 303 concorrentes com 524 pontos e conquistou uma segunda medalha de ouro consecutiva. Ele disse aos repórteres que estava satisfeito com o 14º lugar, que 524 pontos eram mais do que esperava e que esperava que sediar a olimpíada despertasse mais interesse por computadores entre os jovens tailandeses. Quinze anos depois, Pasin Manurangsi é um dos investigadores cujo trabalho consiste em dizer ao resto da ciência da computação quais problemas são sem esperança.

O arco da Olimpíada

O histórico competitivo de Manurangsi lê-se como uma experiência controlada de melhoria. Na IOI de 2009 na Bulgária, ele marcou 516 pontos e terminou em 67º de 301, levando a prata. Em 2010, no Canadá, ele marcou 704 e terminou em 12º de 297, levando o ouro. Em 2011, em solo natal, ele levou o ouro novamente enquanto a Tailândia ganhava a medalha de ouro por equipas na competição que sediou pela primeira vez. Três participações, dois ouros e uma prata, e um salto de cinquenta e cinco lugares no ranking mundial entre a sua primeira e segunda tentativas: a trajetória de alguém que tratou uma derrota como um documento de especificação em vez de um veredito.

MIT, e o problema de chegar perto o suficiente

Manurangsi tirou tanto o bacharelado quanto o mestrado no Massachusetts Institute of Technology (MIT), onde o seu trabalho de mestrado, supervisionado por Dana Moshkovitz, dizia respeito a algoritmos de aproximação para jogos de projeção. Essa escolha de tópico definiu a direção de tudo o que se seguiu. A aproximação é o compromisso pragmático da disciplina: quando um problema não pode ser resolvido exatamente num tempo razoável, contenta-se com uma resposta garantida dentro de algum fator da melhor. A questão interessante, e à qual Manurangsi voltava constantemente, é quão boa essa garantia pode ser antes de colidir com uma parede matemática.

Berkeley: O país entre P e NP

Ele completou o seu doutorado na Universidade da Califórnia, Berkeley, em maio de 2019, co-supervisionado por Luca Trevisan e Prasad Raghavendra, com Nikhil Srivastava no comité. A tese foi intitulada Approximation and Hardness: Beyond P and NP (Aproximação e dureza: para além de P e NP), e a sua ambição é visível no título. A teoria da complexidade clássica classifica os problemas em tratáveis (P) e notoriamente difíceis (NP-completos). A dissertação de Manurangsi caçou deliberadamente no terreno que essas categorias não cobrem: problemas que não estão em P nem são conhecidos como NP-difíceis, problemas parametrizados como o conjunto k-dominante, k-clique, k-biclique, rede Steiner dirigida e problemas de redes, e — o mais contraintuitivo — problemas que se situam confortavelmente dentro de P, como o par mais próximo e o produto interno máximo, mas que resistem a uma aproximação rápida de qualquer maneira. O resumo afirma que o trabalho resolve duas questões abertas de longa data na complexidade parametrizada e entrega os melhores fatores de inaproximabilidade conhecidos para vários problemas. É uma tese sobre desenhar fronteiras, não cruzá-las.

A parede do k-subgrafo mais denso

O único resultado que fez o seu nome diz respeito ao k-subgrafo mais denso: dado um grafo, encontrar os k nós embalados mais firmemente com conexões. Manurangsi provou que, sob a hipótese do tempo exponencial, nenhum algoritmo de tempo polinomial pode alcançar uma razão de aproximação melhor do que n à potência 1/(log log n) elevada a uma constante — e que sob a suposição mais forte Gap-ETH, a barreira aperta-se para n^f(n) para qualquer função f tendendo a zero, o que é quase uma dureza polinomial. Crucialmente, a construção tem o que o campo chama de completude perfeita: distingue grafos que contêm genuinamente um k-clique de grafos onde cada k-subgrafo é esparso. O artigo ganhou o prémio Danny Lewin de melhor artigo estudantil na STOC 2017, a conferência de teoria emblemática da disciplina.

Google, privacidade e divisão justa

Desde julho de 2019, Manurangsi tem sido um cientista de pesquisa no Google Research, onde as suas áreas listadas são algoritmos e teoria, inteligência de máquina e anti-abuso, e onde acumulou mais de cem publicações. O centro de gravidade mudou da inaproximabilidade pura para a privacidade diferencial, teoria de aprendizagem e escolha social computacional — divisão justa, divisão de consenso, agregação de ranks privados, geração de dados sintéticos. Um resultado recente mostra que a divisão de consenso até O(√(n log n)) bens existe sempre para n agentes com utilidades monótonas, melhorando um limite anterior. Os prémios continuaram a chegar: Melhor Artigo na WAOA 2021, Melhor Artigo Estudantil na ALT 2021, um Melhor Artigo e uma Menção Honrosa de Melhor Artigo na FORC 2026, mais reconhecimento de comité de programa distinto no IJCAI em 2021 e 2023 e status de revisor topo na NeurIPS 2023.

A viagem de volta

Desde 2022, ele tem feito parte das equipas de treino para a Olimpíada de Informática da Tailândia e os seus campos de olimpíada matemática, e serviu como membro convidado da delegação da Tailândia na IOI 2024. Desde 2023, ele também tem sido professor adjunto na CMKL University, ensinando algoritmos, estruturas de dados e algoritmos de preservação de privacidade. O pipeline que o produziu é um que ele agora ajuda a gerir.

Por que Pasin é chamado de génio

A qualidade cognitiva em questão aqui é incomumente específica, e não é velocidade bruta. O sucesso olímpico recompensa a resolução rápida e precisa de problemas sob pressão do tempo; a dureza da aproximação recompensa quase o oposto — a paciência para construir uma redução elaborada provando que toda uma classe de algoritmos está condenada. Manurangsi é raro por ter feito ambos a um alto nível, e a tese de Berkeley é a prova: marca território que a maioria dos investigadores evita precisamente porque resultados negativos são mais difíceis de publicar e mais difíceis de acertar. Um único deslize lógico numa redução invalida tudo.

O contra-argumento honesto é substancial. Nada no registo disponível — a sua própria página inicial, perfil do Google Research, dissertação ou a cobertura de imprensa tailandesa contemporânea — usa a palavra "génio" sobre ele. As suas honras são prémios de pares de comités de conferência, que reconhecem o melhor artigo numa sala, não uma mente para as eras. A ciência da computação teórica é também implacavelmente colaborativa; os seus cem e mais artigos são o produto de coautoria, seminários e um grupo de Berkeley liderado por dois dos teóricos da complexidade mais fortes do campo. O seu histórico na IOI, embora excelente, inclui um 67º lugar. O que pode ser dito sem inflação é mais estreito e mais interessante: ele é um profissional de primeira linha num dos cantos tecnicamente mais exigentes da matemática, e o seu resultado definidor fechou uma questão que estava aberta há anos. Isso não é o mesmo que ser um génio, e ele nunca afirmou que o seja.

Perspetiva

A carreira de Manurangsi tem uma forma incomum para um teórico: as provas de impossibilidade vieram primeiro, o trabalho de privacidade aplicada em segundo. A mudança para privacidade diferencial e divisão justa sugere alguém que, tendo estabelecido onde estão as paredes, preferiria agora construir dentro delas. O treino da olimpíada tailandesa pode revelar-se o legado mais duradouro — um país que sediou a IOI uma vez, e agora cultiva as pessoas que a ganham.