Frances Foong Yao

Frances Foong Yao

Department of Computer Science
City University of Hong Kong
83 Tat Chee Avenue, Kowloon
Hong Kong
Tel: 852-2194-2907
csfyao@cityu.edu.hk


Profile

Frances Yao received a B.S. in Mathematics from National Taiwan University in 1969, and a Ph.D. in Mathematics from MIT in 1973. After serving on the Computer Science faculty at University of Illinois, Brown University and Stanford University, she joined Xerox PARC (Palo Alto Research Center) in 1979. At Xerox PARC she managed the Theoretical Computer Science area and served as Principal Scientist until 1999. She joined the Computer Science Department of City University of Hong Kong in August of 2003.

Over the years, her research interests have spanned the spectrum of theoretical computer science, with specialty in computational geometry and combinatorial algorithms. Her papers Speed-up in Dynamic Programming and Finite-Resolution Computational Geometry, are each considered genesis of an important new subfield of algorithm study and has attracted a strong following over the years. On the more practical side, she has had many collaborations on projects in computer graphics, image compression and computer systems.

Frances Yao has chaired and served frequently on program committees of the premier conferences in theoretical computer science: STOC, FOCS and SODA. She has also served on the editorial boards of numerous journals including Theoretical Computer Science, Journal of Algorithms, and SIAM Review.

Research Interests

  • Algorithms & Complexity
  • Computational Geometry & Computer Graphics
  • Data Security & Cryptography

    Honors and Awards

  • Fellow, American Association for the Advancement of Science
  • Lester R. Ford Award, The Mathematical Association of America
  • Recognition of Service Award, The Association for Computing Machinery
  • Xerox Achievement Award

    Selected Publications

  • `Information bounds are weak in the shortest distance problem,' (with R. L. Graham and A. C. Yao) Journal of ACM 27 (1980), 428-444.
  • `Efficient dynamic programming using quadrangle inequalities,' Proc. 12th ACM Annual Symp. on Theory of Computing, April 1980, 429-435.
  • `On translating a set of rectangles,' (with L. J. Guibas), Advances in Computing Research 1 (1983), 61-77.
  • `On the priority approach to hidden-surface algorithms,' Proc. 21st Annual Symp. on Foundations of Computer Science, October 1980, 301-307.
  • `Speed-up in dynamic programming,' SIAM J. on Algebraic and Discrete Methods 3 (1982), 532-540.
  • `Finite-resolution computational geometry,' (with D. Greene), Proc. 27th Annual Symp. on Foundations of Computer Science, October 1986, 143-152.
  • `Partitioning space for range queries,' (with D. Dobkin, H. Edelsbrunner and M. S. Paterson), SIAM J. on Computing 18 (1989), 371-384.
  • Computational Geometry, Chapter in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Elsevier Science Publishers B. V., Amsterdam (1990), 345-389.
  • `Binary space partitions with applications to hidden-surface removal and solid modelling,' (with M. S. Paterson), Discrete & Computational Geometry 5 (1990), 485-504.
  • `A scheduling model for reduced CPU energy,' (with A. Demers and S. Shenker), Proc. 36th Annual Symp. on Foundations of Computer Science (1995), 374-382.
  • `Progressive Ziv-Lempel encoding of synthetic images,' (with D. Greene, M. Vishwanath, and T. Zhang), Data Compression Conference (DCC) (1997), 441.
  • `Approximating shortest superstrings,' (with S. Teng), SIAM J. on Computing 26 (1997), 410-417.
  • `A linear algorithm for optimal context clustering with application to bi-level image coding,' (with D. Greene and T. Zhang), Proceedings of 1998 International Conference on Image Processing 1 (1998), 508-511.

    Some Recent Publications

  • `Design and analysis of password-based key derivation functions,' (with Yiqun Lisa Yin), IEEE Transactions on Information Theory 51 (2005), 3292- 3297.
  • `An efficient algorithm for computing optimal discrete voltage schedules,' (with Minming Li), SIAM Journal on Computing 35 (2005), 658-671 .
  • `Min-energy voltage allocation for tree-structured tasks,' (with Minming Li and Becky Jie Liu), Journal of Combinatorial Optimization 11(3)(2006), 305-319.
  • `Discrete and continuous min-energy schedules for variable voltage processors,' (with Minming Li and Andrew C Yao), Proceedings of the National Academy of Sciences USA 103 (2006), 3983-3987.
  • `Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks,' (with P.-J. Wan, C. -W. Yi and X. Jia), MOBIHOC 2006.

  • `A distributed and efficient flooding scheme using 1-hop information in mobile ad hoc networks,' (with Hai Liu, Xiaohua Jia, Pengjun Wan and Xinxin Liu), IEEE Transactions on Parallel and Distributed Systems 18(5)(2007), 658-671.

  • `Optimal tree structure for group key management with batch updates,' (with Ronald L Graham and Minming Li), SIAM Journal on Discrete Mathematics 21(2) (2007), 532-547.
  • `k-nearest-neighbor clustering and percolation theory,' (with Shang-Hua Teng), Algorithmica 49 (3) (2007), 192-211.