CUHK
News Centre

Three young scholars of the Department of Computer Science and Engineering at The Chinese University of Hong Kong (CUHK) were recently awarded international prizes. Prof. Lau Lap-chi was awarded the Canadian Mathematical Society (CMS) Doctoral Prize, Prof. Zhang Shengyu and Prof. Patrick P.C. Lee received the best paper award in the International Colloquium on Automata, Languages and Programming (ICALP), and the ACM CoNext 2008. The CMS Doctoral Prize recognizes the outstanding performance of a doctoral graduate of a Canadian University. The ICALP is one of the most significant conferences in theoretical computer sciences covering all major theory spectrums, and the ACM CoNext Conference is a major forum that encourages international research communities to exchange novel ideas that shape the future of computer network technologies. These three scholars were recently recruited to join the faculty of CUHK, showing the high standard set in the recruitment effort and the attraction of the University to the best young rising stars in research.

The first computer scientist who received the CMS Doctoral Prize, Prof. Lau Lap-chi’s groundbreaking thesis tackles fundamental and difficult problems concerning connectivity in graphs, which often have applications in communication networks. Many graph connectivity problems are NP-hard, meaning that there is no efficient algorithm for finding an optimal solution to the problems. He focuses on the design of efficient approximation algorithms, in which the returned solutions are guaranteed to be close to the optimal solutions. Particularly, he studied the Steiner Tree Packing problem, a network multicasting problem in which a sender aims to send out data to a set of receivers as efficiently as possible. Prof. Lau successfully found an efficient approximation algorithm for this problem, leading to further significant developments in this area.

As quantum computers can easily break cryptographic systems widely used on the internet, a fundamental research question is to understand which cryptosystems are secure from attacks by quantum computers in computer science. A central concept in cryptography is zero-knowledge protocols, which show one’s identity without leaking the password. In the paper, Prof. Zhang and his collaborators give an efficient procedure which transforms zero-knowledge protocols secure in the classical setting to another that is probably also secure in the quantum setting. Moreover, the resulting protocols are classical and are therefore secure from potential attacks by quantum computers.

In view of the rate anomaly problem suffered by currently deployed IEEE 802.11 WiFi networks in which stations transmitting at low data rates have dramatically reduced the throughput of stations transmitting at high data rates, Prof. Patrick P.C. Lee and his collaborators propose a practical, deployable system called SoftRepeater. The system allows higher-rate WiFi stations to opportunistically transform themselves into repeaters and relay data for lower-rate stations, and the repeater functionality to be enabled only when appropriate. SoftRepeater can also run directly on today’s 802.11 infrastructure networks. Through simulation and testbed experiments, SoftRepeater can improve cumulative throughput by about two times.

Although wireless networking has become popular among corporations and home networks, users still occasionally suffer from the poor performance of wireless data transfer due to inherently unstable wireless medium. SoftRepeater provides a practical solution to improve the throughput performance of wireless data transfer.

CUHK Pro-Vice-Chancellor Prof. Kenneth Young is pleased with the outstanding achievements of the three scholars. “Information sciences are the foundation for the development of Information and Communications Technology (ICT), a vital tool for participating in global markets, improving service delivery, and tapping opportunities for development. In the era of globalization, information sciences play a vital role in technological and societal developments. In view of this, the University has identified information sciences as one of the five strategic areas for focused research. The awards of these scholars once again affirm our excellence in information sciences research,” he remarked.

CUHK strives to reach new frontiers and to achieve international standards in research in order to become a first-class comprehensive research university. To advance information sciences development, the Institute of Theoretical Computer Science and Communications led by its director, Prof. Andrew Yao Chi-chih, was established in 2007 at CUHK. Prof. Yao is a Distinguished Professor-at-Large at CUHK, and also a Turing Award Winner, an award which is widely regarded as the Nobel Prize of computer science. Under Prof. Yao’s leadership, the Institute aims to encourage international research collaboration and exchange, and to nurture young scientists and students. All of the three award-winning scholars are also members of the Institute.