Parallel models of computation and algorithms

点击翻译按钮获取中文摘要

My research focuses on parallel computation, with a particular emphasis on models and algorithms. Its goal is to achieve a better understanding of a number of fundamental issues pertaining to parallel problem solving, in theory and in practice. Recently, I concentrated my efforts on a new application of the principles of parallel computation, namely, unconventional computing, with its two branches: unconventional computers and unconventional computational problems. This is a proposal to continue and extend my previous work in the following directions: (1) Evolving computational systems. The role of physical time and physical space in computing, and the properties of computational problems that depend on them, are to be investigated. This will introduce new paradigms to the theory of computation and promote the study of certain problems whose scientific and economic importance can only grow with the widespread and diverse uses of computers (from the real-time monitoring and analysis of critical applications on Earth, to the exploration of outer space). (2) Quantum computing. The objective of my research here is to discover computational problems for which a quantum computer is more powerful in principle (not just faster) than a classical computer, in the sense that these problems can be solved by the former but not the latter. (3) Applications to wireless sensor networks. In this study, the main questions to be addressed involve algorithms for: placement of data collectors, finding maximal overlapping regions of a set of spheres in three dimensions, computing disjoint dominating sets, and target monitoring. (4) Applications to network security. The ideas of quantum cryptography are to be applied to wireless sensor networks for the protection of sensitive data. A long term goal is to solve the problem of identity theft in more general situations involving secrecy and authentication. This research will train 8 PhDs, 9 MScs, 5 undergraduates and 3 postdoctoral fellows. Their knowledge and expertise in ubiquitous parallel computation, quantum computing, sensor networks, and computer security will help maintain Canada's competitiveness and leadership in information and communication technology.