Parallel models of computation and algorithms

我的研究重点是并行计算，特别强调模型和算法。它的目标是在理论和实践中更好地理解与并行问题解决有关的一些基本问题。最近，我集中精力研究并行计算原理的一个新应用，即非常规计算，它有两个分支：非常规计算机和非常规计算问题。这是一个在以下方向上继续和扩展我以前工作的建议：(1)不断发展的计算系统。物理时间和物理空间在计算中的作用，以及依赖于它们的计算问题的性质，将被研究。这将为计算理论引入新的范例，并促进对某些问题的研究，这些问题的科学和经济重要性只会随着计算机的广泛和多样化使用而增长（从地球上关键应用的实时监测和分析，到外层空间的探索）。(2)量子计算。我在这里研究的目的是发现量子计算机在原则上比经典计算机更强大（不仅仅是更快）的计算问题，因为这些问题可以由前者解决，而不是后者。(3)无线传感器网络的应用。在本研究中，要解决的主要问题包括：数据收集器的放置，在三维空间中寻找一组球体的最大重叠区域，计算不相交支配集以及目标监控。(4)网络安全应用。量子密码学的思想将被应用于无线传感器网络，以保护敏感数据。长期目标是解决涉及保密和身份验证的更普遍情况下的身份盗窃问题。本项目将培养博士8人、硕士9人、本科生5人、博士后3人。他们在无处不在的并行计算、量子计算、传感器网络和计算机安全方面的知识和专业知识将有助于保持加拿大在信息和通信技术方面的竞争力和领导地位。

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.