Frances Yao

After receiving a B.S. in mathematics from National Taiwan University in 1969, Yao did her Ph.D. studies under the supervision of Michael J. Fischer at the Massachusetts Institute of Technology, receiving her Ph.D. in 1973. She then held positions at the University of Illinois at Urbana-Champaign, Brown University, and Stanford University, before joining the staff at the Xerox Palo Alto Research Center in 1979 where she stayed until her retirement in 1999.

In 2003, she came out of retirement to become the Head and a Chair Professor of the Department of Computer Science at City University of Hong Kong, which she held until June 2011. She is a Fellow of the American Association for the Advancement of Science; in 1991, she and Ronald Graham won the Lester R. Ford Award of the Mathematical Association of America for their expository article, A Whirlwind Tour of Computational Geometry.[2]

Yao's husband, Andrew Yao, is also a well-known theoretical computer scientist and Turing Award winner.[3][4][5][6][7]

Much of Yao's research has been in the subject of computational geometry and combinatorial algorithms; she is known for her work with Mike Paterson on binary space partitioning,[8] her work with Dan Greene on finite-resolution computational geometry,[9] and her work with Alan Demers and Scott Shenker on scheduling algorithms for energy-efficient power management.[10]

More recently she has been working in cryptography. Along with her husband Andrew Yao and Wang Xiaoyun, they found new attacks on the SHA-1 cryptographic hash function.[11][12]

• Chung, F. R. K.; Erdős, P.; Graham, R. L.; Ulam, S. M.; Yao, F. F. (1979), "Minimal decompositions of two graphs into pairwise isomorphic subgraphs", Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), Congressus Numerantium, XXIII–XXIV, Winnipeg, Manitoba: Utilitas Mathematica, pp. 3–18, MR 0561031.
• Graham, Ronald L.; Yao, F. Frances (1983), "Finding the convex hull of a simple polygon", Journal of Algorithms, 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR 0729228.
• Yao, A. C.; Yao, F. F. (1985), "A general approach to d-dimensional geometric queries", Proceedings of 17th Symposium on Theory of Computing (STOC 1985), New York, NY, USA: ACM, pp. 163–168, doi:10.1145/22145.22163, ISBN 978-0-89791-151-1, S2CID 6090812.
• Greene, Daniel H.; Yao, F.Frances (October 1986), "Finite-resolution computational geometry", Proceedings of 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pp. 143–152, doi:10.1109/SFCS.1986.19, ISBN 978-0-8186-0740-0, S2CID 2624319.
• Graham, Ron; Yao, Frances (1990), "A whirlwind tour of computational geometry", American Mathematical Monthly, 97 (8): 687–701, doi:10.2307/2324575, JSTOR 2324575, MR 1072812.
• Paterson, Michael S.; Yao, F. Frances (1990), "Efficient binary space partitions for hidden-surface removal and solid modeling", Discrete and Computational Geometry, 5 (5): 485–503, doi:10.1007/BF02187806, MR 1064576.
• Yao, Frances; Demers, Alan; Shenker, Scott (October 1995), "A scheduling model for reduced CPU energy", Proceedings of 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), IEEE Computer Society, pp. 374–382, doi:10.1109/SFCS.1995.492493, ISBN 978-0-8186-7183-8, S2CID 5381643.
• Huang, S.C.; Wan, Peng-Jun; Vu, C.T.; Li, Yingshu; Yao, F. (May 2007), "Nearly constant approximation for data aggregation scheduling in wireless sensor networks", Proceedings of 26th IEEE International Conference on Computer Communications (IEEE INFOCOM 2007), pp. 366–372, CiteSeerX 10.1.1.298.8186, doi:10.1109/INFCOM.2007.50, ISBN 978-1-4244-1047-7, S2CID 1984413.

• F. Frances Yao at DBLP Bibliography Server