Andrew Yao
Meer info
- Geboren
- 1946, Shanghai
- Prijs
- Turing Award 2000
- Bekend van
- Miljonairsprobleem, garbled circuits, communicatiecomplexiteit
De theoreticus die zich afvroeg hoe twee miljonairs kunnen uitvinden wie van hen rijker is zonder dat een van beiden zijn vermogen prijsgeeft.
Andrew Chi-Chih Yao promoveerde in de natuurkunde aan Harvard en daarna nog een keer in de informatica, om vervolgens te belanden bij de complexiteitstheorie. In 1979 legde hij de basis van de communicatiecomplexiteit en in 1982 formuleerde hij het miljonairsprobleem: twee partijen willen een functie van hun geheime invoer berekenen zonder die invoer aan elkaar te tonen. Zijn antwoord, garbled circuits, versleutelt een volledig booleaans circuit poort voor poort, zodat het kan worden doorgerekend zonder dat een tussenwaarde zichtbaar wordt. Dat was het startschot voor secure multiparty computation, die Goldreich, Micali en Wigderson in 1987 veralgemeniseerden.
De Turing Award volgde in 2000, mede voor de complexiteitsgebaseerde theorie van pseudowillekeurigheid. In 2004 verruilde hij Princeton voor Tsinghua in Peking, waar zijn selectieve opleiding, de Yao Class, inmiddels een flink deel van de Chinese informatici heeft afgeleverd. Ook droeg hij bij aan de circuittheorie van quantumcomputing.