# Frances Yao

Frances Foong Chu Yao (en chinois : 储枫) est une mathématicienne et informaticienne américaine d'origine chinoise. Elle est professeur titulaire à l'Institute for Interdisciplinary Information Sciences (en) (IIIS) de l'Université Tsinghua. Elle était professeur titulaire et directeur du département d'informatique de l'université municipale de Hong Kong, où elle est maintenant (en 2018) professeur honoraire.

## Biographie

Après avoir obtenu un B.S. en mathématiques à l'université nationale de Taïwan en 1969, Yao étudie au Massachusetts Institute of Technology, et y obtient en 1973 un Ph.D. sous la supervision de Michael J. Fischer avec une thèse intitulée « On Lower Bounds for Selection Problems ». Elle occupe ensuite des postes à l'université de l'Illinois à Urbana-Champaign, l'université Brown et l'université Stanford. Elle rejoint ensuite le Palo Alto Research Center en 1979, où elle travaille comme Principal Scientist et directeur de la Theoretical Computer Science Area jusqu'à sa retraite en 1999.
En 2003, elle sort de sa retraite et devient directeur et professeur titulaire du département d'informatique à la City University of Hong Kong, poste qu'elle occupe jusqu'en juin 2011. Elle est Fellow de l’Association américaine pour l'avancement des sciences ; en 1991, elle obtient, avec Ronald Graham, le prix Lester Randolph Ford de la Mathematical Association of America pour leur article de synthèse A Whirlwind Tour of Computational Geometry.
Frances Foong ChuYao est mariée avec Andrew Yao, informaticien théoricien bien connu, lauréat du prix Turing$^,$$^,$$^,$.

## Recherche

Une grande partie des travaux de recherche de Yao a porté sur des sujets de géométrie algorithmique et des alborithmes combinatoires ; elle est connue pour ses recherches, avec Michael Stewart Paterson sur le problème de la partition binaire de l'espace, son travail avec Dan Greene sur la résolution finie en géométrie algorihmique et ses recherches, avec Alan Demers et Scott Shenker sur des algorithmes d'ordonnancement dans les systèmes d'exploitation dans la gestion électrique efficace.
Plus récemment; elle a travaillé en cryptographie. Avec son mari Andrew Yao et Wang Xiaoyun, elle a découvert de nouvelles attaques sur la fonction de hachage cryptographique SHA-1$^,$.

## Publications (sélection)

* Fan Chung, Paul Erdős, Ronald L. Graham, Stanislaw M. Ulam et F. Frances Yao, « Minimal decompositions of two graphs into pairwise isomorphic subgraphs », Congressus Numerantium, Winnipeg, Manitoba, vol. XXIII–XXIV « Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979) »,‎ 1979, p. 3–18 (MR 561031).
* Ronald L. Graham et F. Frances Yao, « Finding the convex hull of a simple polygon », Journal of Algorithms, vol. 4, n$^o$ 4,‎ 1983, p. 324–331 (DOI 10.1016/0196-6774(83)90013-5, MR 729228).
* Andrew C. Yao et F. Frances Yao, « A general approach to d-dimensional geometric queries », ACM, New York, NY, USA,‎ 1985, p. 163–168 (ISBN 0-89791-151-2, DOI 10.1145/22145.22163).
* Daniel H. Greene et F. Frances Yao, « Finite-resolution computational geometry », Proceedings of 27th Annual Symposium on Foundations of Computer Science (FOCS 1986),‎ octobre 1986, p. 143–152 (DOI 10.1109/SFCS.1986.19).
* Ronald L. Graham et F. Frances Yao, « A whirlwind tour of computational geometry », American Mathematical Monthly, vol. 97, n$^o$ 8,‎ 1990, p. 687–701 (DOI 10.2307/2324575, MR 1072812, lire en ligne).
* Michael S. Paterson et F. Frances Yao, « Efficient binary space partitions for hidden-surface removal and solid modeling », Discrete and Computational Geometry, vol. 5, n$^o$ 5,‎ 1990, p. 485–503 (DOI 10.1007/BF02187806, MR 1064576).
* F. Frances Yao, Alan Demers et Scott Shenker, « A scheduling model for reduced CPU energy », IEEE Computer Society,‎ octobre 1995, p. 374–382 (DOI 10.1109/SFCS.1995.492493).
* S.C. Huang, Peng-Jun Wan, C. T. Vu, Yingshu Li et F. Frances Yao, « Nearly constant approximation for data aggregation scheduling in wireless sensor networks », Proceedings of 26th IEEE International Conference on Computer Communications (IEEE INFOCOM 2007),‎ mai 2007, p. 366–372 (DOI 10.1109/INFCOM.2007.50).