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

  • `Wireless Link Scheduling under Physical Interference Model,' (with Peng-Jun Wan, Ophir Frieder, Xiaohua Jia, Xiaohua Xu and Shaojie Tang), accepted by INFOCOM 2011.
  • `Multiflows in Multi-Channel Multi-Radio Multihop Wireless Networks,' (with Peng-Jun Wan, Yu Cheng and Zhu Wang), accepted by INFOCOM 2011.
  • `Approximate Capacity Subregions of Uniform Multihop Wireless Networks,' (with Peng-Jun Wan, Lixin Wang, Ai Huang and Minming Li), INFOCOM 2010.
  • `Minimum CDS in Multihop Wireless Networks with Disparate Communication Ranges,' (with Lixin Wang and Peng-Jun Wan), WASA 2010.
  • `Algorithmic Problems in Computer and Network Power Management,', FAW 2009.
  • `Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks,' (with Minming Li and Peng-Jun Wan), ISAAC 2009.
  • `Maximum Independent Set of Links under Physical Interference Model,' (with Peng-Jun Wan and Xiaohua Jia), WASA 2009.
  • `Asymptotic Critical Transmission Radii for Greedy Forward Routing in Wireless Ad Hoc Networks,' (with Peng-Jun Wan, Chih-Wei Yi, Lixin Wang and Xiaohua Jia), IEEE Transactions on Communications 57 (5) (2009), 1433-1443.
  • `A note on the feasibility of generalised universal composability,' (with Andrew Chi-Chih Yao and Yunlei Zhao), Mathematical Structures in Computer Science 19 (1) (2009), 193-205.
  • `Approximately optimal trees for group key management with batch updates,' (with Minming Li, Ze Feng, Nan Zang and Ronald L. Graham), Theoretical Computer Science 410 (11) (2009), 1013-1021.
  • `A note on universal composable zero-knowledge in the common reference string model,' (with Andrew Chi-Chih Yao and Yunlei Zhao), Theoretical Computer Science 410 (11) (2009), 1099-1108.
  • `On the Longest RNG Edge of Wireless Ad Hoc Networks,' (with Peng-Jun Wan, Lixin Wang and Chih-Wei Yi), ICDCS 2008.
  • `Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks,' (with Peng-Jun Wan and Lixin Wang), ICDCS 2008.
  • `Improved asymptotic bounds on critical transmission radius for greedy forward routing in wireless ad hoc networks,' (with Lixin Wang and Chih-Wei Yi), MOBIHOC 2008.
  • `On minimum m -connected k -dominating set problem in unit disc graphs,' (with Weiping Shang, Peng-Jun Wan and Xiaodong Hu), Journal of Combinatorial Optimization 16 (2) (2008), 99-106.
  • `Optimizing deletion cost for secure multicast key management,' (with Zhi-Zhong Chen, Ze Feng and Minming Li), Theoretical Computer Science 401 (1-3) (2008), 52-61.
  • `Lower bounds and new constructions on secure group communication schemes,' (with Scott C.-H. Huang, Minming Li and Weili Wu), Theoretical Computer Science 407 (1-3) (2008), 511-523.
  • `Algorithms for Minimum m -Connected k -Dominating Set Problem,' (with Weiping Shang, Peng-Jun Wan and Xiaodong Hu), COCOA 2007.
  • `Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors,' CPM 2007.
  • `Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor Networks,' (with Scott C.-H. Huang, Peng-Jun Wan, Chinh T. Vu and Yingshu Li), INFOCOM 2007.
  • `Approximately Optimal Trees for Group Key Management with Batch Updates,' (with Minming Li, Ze Feng and Ronald L. Graham), TAMC 2007.
  • `A Note on Universal Composable Zero Knowledge in Common Reference String Model,' (with Andrew Chi-Chih Yao and Yunlei Zhao), TAMC 2007.
  • `A Note on the Feasibility of Generalized Universal Composability,' (with Andrew Chi-Chih Yao and Yunlei Zhao), TAMC 2007.
  • `Algorithms for minimum m-connected k-tuple dominating set problem,' (with Weiping Shang, Peng-Jun Wan and Xiaodong Hu), Theoretical Computer Science 381 (1-3) (2007), 241-247.
  • `k-nearest-neighbor clustering and percolation theory,' (with Shang-Hua Teng), Algorithmica 49 (3) (2007), 192-211.
  • `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.
  • `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.
  • `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.
  • `Min-energy voltage allocation for tree-structured tasks,' (with Minming Li and Becky Jie Liu), Journal of Combinatorial Optimization 11(3)(2006), 305-319.
  • `An efficient algorithm for computing optimal discrete voltage schedules,' (with Minming Li), SIAM Journal on Computing 35 (2005), 658-671 .
  • `Design and analysis of password-based key derivation functions,' (with Yiqun Lisa Yin), IEEE Transactions on Information Theory 51 (2005), 3292- 3297.

  •