Foundations of Computer Science

"Foundations" refers to the theoretical building blocks underlying all of computer science. Our group studies topics ranging from the capabilities and properties of classical and modern computers to those of exciting emerging areas such as quantum computers. These studies include questions such as:

• What problems cannot be solved by modern computers, and how can we identify them?
• Are there problems, for example in areas such as linear algebra, number theory, and graph theory, that cannot be solved efficiently on a computer?
• How can randomization be used effectively to solve problems faster but still reliably?
• How can multi-core and parallel processor architectures be used effectively, while ensuring that all processors have a consistent view of applications' data?
• How can the physical properties of quantum mechanics be harnessed to efficiently solve problems that are currently believed to be computationally infeasible using classical computing?
• What are the theoretical bases of modern programming languages, and how can we use this theory to devise more effective means of programming modern computers?

These issues are key to understanding the limitations and possibilities of computer technology, and for guiding practitioners' decisions and choices of algorithms in more applied areas. The skills students obtain by studying these sorts of questions, including analysis of algorithms, computability theory, complexity theory, and data structures and algorithm design techniques, are essential components of a quality computer science education.

Our group has expertise in the following areas:

• Algorithms and quantum computations
• Cryptography and computational number theory
• Efficient Algorithms and Complexity Theory

Join the group's mailing list cs-theory announcing seminars and events.

Algorithms and quantum computations

We conduct research in algorithmic aspects of quantum mechanical systems. We study systems based on quantum mechanical principles and how they differ from traditional computational systems. Our research areas include quantum algorithmics, quantum complexity theory, quantum communication complexity, quantum information theory, and quantum computer simulations of quantum mechanical systems. Research in quantum computing is interdisciplinary in nature and our work is being conducted in close collaboration with researchers in physics and mathematics.

Research faculty:
Peter Høyer (http://www.cpsc.ucalgary.ca/~hoyer)

Affiliated research group:
Institute for Quantum Information Science (http://www.iqis.org/)

Cryptography and computational number theory

Our research in cryptography focuses on the exploration of mathematically and computationally difficult problems as a source of secure communications. In particular, we investigate the suitability of certain number-theoretic structures and problems as bases for public-key cryptosystems, enabling applications such as secure cryptographic key exchange and digital signatures. We are especially interested in problems related to elliptic and hyperelliptic curves, algebraic number fields, and function fields, as well as cryptosystems based on these problems. The efficiency of such cryptographic systems is tested by implementing the best-known algorithms and devising improvements. The security is tested by developing sequential and distributed algorithms for solving the underlying number-theoretic problem.

Research faculty:
Michael Jacobson (http://cpsc.ucalgary.ca/~jacobs)
Payman Mohassel (http://cpsc.ucalgary.ca/~pmohasse)
Renate Scheidler (http://math.ucalgary.ca/~rscheidl)

Affiliated research groups:
Centre for Information Security and Cryptography (http://www.cisac.ucalgary.ca/)
iCORE Information Security Lab (http://icis.cpsc.ucalgary.ca/)

Efficient Algorithms and Complexity Theory

We develop methods for the design of efficient algorithms, and we analyze the complexity of selected problems. Our research covers a broad range of algorithmic areas, with a focus on probabilistic methods. Algorithmic research areas include the design of fundamental data structures, hashing methods, network algorithms, and algorithms for distributed computing. We study the complexity of selected fundamental problems for various computation models, such as distributed shared memory models, branching programs, or multi-party communication.

Research faculty:
Philipp Woelfel (http://www.cpsc.ucalgary.ca/~woelfel)