Login [Center] Logout Join Us Guidelines  I  中文  I  CQI

Frances Foong Yao

Chair Professor
Institute for Interdisciplinary Information Sciences, Tsinghua University

Computational Geometry and Combinatorial Algorithms



Frances Yao(储枫) is currently a member of the Chair Professor Team at IIIS of Tsinghua University, and an Honorary Professor with the City University of Hong Kong. She received her 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, where she managed the Theoretical Computer Science area and served as Principal Scientist. In 2003 she joined the Computer Science Department of the City University of Hong Kong and served as Head until 2011.

Frances Yao’s research interests lie in the efficient algorithm design for various domains including energy-efficient computing, computational geometry, sensor and wireless networks. For example, her papers on variable-voltage energy-efficient scheduling [1], binary-space partitions [2], finite-resolution computational geometry [3] and speed-up in dynamic programming [4] are each considered as genesis of an important new subfield of algorithm study and they have attracted strong followings over the years. On the more practical side, she has also collaborated 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 Journal of Algorithms, Discrete & Computational Geometry, SIAM Review, SIAM Journal on Discrete Mathematics, and Theoretical Computer Science. She is a Fellow of American Association for the Advancement of Science, and is a recipient of the Lester R. Ford Award from the Mathematical Association of America. 

Highly cited works: 

[1] F. Yao, A. Demers and S. Shenker, A scheduling model for reduced CPU energy, Proc. 36th Annual Symp. on Foundations of Computer Science (1995), 374-382.

[2] M. S. Paterson and F. Yao, Binary space partitions with applications to hidden-surface removal and solid modeling, Discrete & Computational Geometry 5 (1990), 485-504.

[3] D. Greene and F. Yao, Finite-resolution computational geometry, Proc. 27th Annual Symp. on Foundations of Computer Science, October 1986, 143-152.

[4] F. Yao, Speed-up in dynamic programming, SIAM J. on Algebraic and Discrete Methods 3 (1982), 532-540. 
 

Recent Publications (since 2005)

 1. Maximizing Capacity with Power Control under Physical Interference Model in Duplex Mode, (with P. J. Wan, D. Chen, G. J. Dai, Z. Wang), INFOCOM 2012.

2. Wireless Link Scheduling under Physical Interference Model,(with Peng-Jun Wan, Ophir Frieder, Xiaohua Jia, Xiaohua Xu and Shaojie Tang), INFOCOM 2011

3. Multiflows in Multi-Channel Multi-Radio Multihop Wireless Networks,(with Peng-Jun Wan, Yu Cheng and Zhu Wang), INFOCOM 2011.

4. Minming LiPeng-Jun Wan, F. Frances Yao: Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs. Algorithmica 61(4): 1000-1021 (2011).

5. Approximate Capacity Subregions of Uniform Multihop Wireless Networks,(with Peng-Jun Wan, Lixin Wang, Ai Huang and Minming Li), INFOCOM 2010.

6. Minimum CDS in Multihop Wireless Networks with Disparate Communication Ranges,(with Lixin Wang and Peng-Jun Wan), WASA 2010.

7. Algorithmic Problems in Computer and Network Power Management, FAW 2009.

8. Maximum Independent Set of Links under Physical Interference Model,(with Peng-Jun Wan and Xiaohua Jia), WASA 2009.

9. 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.

10. 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.

11. 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.

12. 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.

13. On the Longest RNG Edge of Wireless Ad Hoc Networks,(with Peng-Jun Wan, Lixin Wang and Chih-Wei Yi), ICDCS 2008.

14. Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks,(with Peng-Jun Wan and Lixin Wang), ICDCS 2008.

15. 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.

16. 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.

17. 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.

18. 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.

19. Algorithms for Minimum m -Connected k -Dominating Set Problem,(with Weiping Shang, Peng-Jun Wan and Xiaodong Hu), COCOA 2007.

20. Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors, CPM 2007.

21. 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.

22. Approximately Optimal Trees for Group Key Management with Batch Updates,(with Minming Li,  Ze Feng and Ronald L. Graham), TAMC 2007.

23. 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.

24. k-nearest-neighbor clustering and percolation theory,(with Shang-Hua Teng), Algorithmica 49 (3) (2007), 192-211.

25. 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.

26. 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.

27. 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.

28. 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.

29. Min-energy voltage allocation for tree-structured tasks,(with Minming Li and Becky Jie Liu), Journal of Combinatorial Optimization 11(3)(2006), 305-319.

30. An efficient algorithm for computing optimal discrete voltage schedules,(with Minming Li), SIAM Journal on Computing 35 (2005), 658-671.

31. Design and analysis of password-based key derivation functions,' (with Yiqun Lisa Yin), IEEE Transactions on Information Theory 51 (2005), 3292- 3297.