Theory of Computation
In the theory of computation area, we use mathematical techniques to understand the nature of computation and to design and analyze algorithms for important and fundamental problems.
The members of the complexity theory group are all interested, in one way or another, in the limitations of computation: What problems are not feasible to solve on a computer? How can the infeasibility of a problem be used to rigorously construct secure cryptographic protocols? What problems cannot be solved faster using more machines? What are the limits to how fast a particular problem can be solved or how much space is needed to solve it? How do randomness, parallelism, the operations that are allowed, and the need for fault tolerance or security affect this?
There is great beauty in theoretical computer science. It is exciting to discover what makes a particular problem difficult, to find a provably optimal solution to a problem, or to discover unexpected connections between seemingly unrelated problems. Theoretical computer science provides important new ways of thinking about computation and provides lasting insights that are applicable to a wide variety of systems. There are also great challenges and opportunities since so many basic problems remain unsolved.
Theory of Distributed Computing
Our research in the theory of distributed computing studies
both shared memory and message passing systems.
We are particularly interested in issues of fault tolerance,
synchronization, and the limits on the computational power
of shared memory primitives.
Applied and Discrete Mathematics
Discrete Mathematics involves the study of the properties, algorithms and applications of mathematical structures built on discrete objects. Our group is primarily concerned with the theoretical and algorithmic issues pertaining to Graph Theory and Combinatorial Designs.
Graph Theory
A graph consists of V (a set of vertices) and E (a set of edges, either ordered or unordered, joining pairs of vertices in V). It is clear that any binary relation may be modeled as a graph; thus, applications of graphs pervade computer science. The interests of our group include computational biology, random structures and the structure of electrical circuits, as well as more traditional graph theory such as graph colouring, perfect graphs, hamiltonicity and generalizations of graphs.
Combinatorial Designs
A combinatorial design is a collection of sets satisfying some given regularity properties of its subsets. The structures can be as loose as regular graphs or as tight as finite projective geometries. The fundamental problems of design theory are the existence, enumeration and generation of designs with given parameters. Applications of designs are found in statistics (the design of experiments), error-correcting codes, computer architecture and cryptography. Our group’s interests include the development and analysis of deterministic and randomized combinatorial search techniques, algebraic methods for the construction of solutions to combinatorial optimization problems, sub-object and/or automorphism-free systems, systems containing specified small partial systems and design invariants.