Frances F. Yao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Frances F. Yao has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Minming Li
Department of Computer Science, City University of Hong Kong, Hong Kong
3 shared publications - Andrew Chi-Chih Yao
Shanghai Qi Zhi Institute
2 shared publications - Yunlei Zhao
Fudan University
2 shared publications - Becky Jie Liu
City University of Hong Kong
1 shared publication - Hao Yuan
Department of Computer Science City University of Hong Kong Kowloon Hong Kong China
1 shared publication - Peng-Jun Wan
Department of Computer Science, Illinois Institute of Technology, Chicago, IL, USA
1 shared publication
Latest Publications
- Open AccessAn $O(n^2)$ Algorithm for Computing Optimal Continuous Voltage SchedulesDynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the discrete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal schedules for the continuous model runs at $O(n^2\log n)$ time for scheduling $n$ jobs. In this paper, we improve the running time to $O(n^2)$ by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best $O(dn\log n)$ to $O(n\log \max\{d,n\})$ where $d$ is the number of allowed speeds.Open AccessAn $O(n^2)$ Algorithm for Computing Optimal Continuous Voltage SchedulesDynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the discrete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal schedules for the continuous model runs at $O(n^2\log n)$ time for scheduling $n$ jobs. In this paper, we improve the running time to $O(n^2)$ by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best $O(dn\log n)$ to $O(n\log \max\{d,n\})$ where $d$ is the number of allowed speeds.
- 15 April 2011
- Published by Springer Nature in Algorithmica
- Vol. 61 (4) , 1000-1021
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
- 15 April 2011
- Published by Springer Nature in Algorithmica
- Vol. 61 (4) , 1000-1021
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
- 6 March 2009
- Published by Elsevier in Theoretical Computer Science
- Vol. 410 (11) , 1099-1108
A note on universal composable zero-knowledge in the common reference string model
- 6 March 2009
- Published by Elsevier in Theoretical Computer Science
- Vol. 410 (11) , 1099-1108
A note on universal composable zero-knowledge in the common reference string model
- 1 February 2009
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 19 (1) , 193-205
A note on the feasibility of generalised universal composability
In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.
- 1 February 2009
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 19 (1) , 193-205
A note on the feasibility of generalised universal composability
In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.
- 22 September 2007
- Published by Springer Nature in Algorithmica
- Vol. 49 (3) , 192-211
k-Nearest-Neighbor Clustering and Percolation Theory
- 22 September 2007
- Published by Springer Nature in Algorithmica
- Vol. 49 (3) , 192-211
k-Nearest-Neighbor Clustering and Percolation Theory
- 1 May 2006
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 11 (3) , 305-319
Min-energy voltage allocation for tree-structured tasks
- 1 May 2006
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 11 (3) , 305-319
Min-energy voltage allocation for tree-structured tasks