Algorithmics
Research in these areas typically involves one or more of the following steps: (i) identification of an interesting problem, (ii) categorization of the problem according to its complexity status, and (iii) searching for an efficient algorithm for handling the problem. The goal is to devise algorithms having prescribed levels of efficiency. This includes polynomial time exact algorithms, improved exponential algorithms, approximation schemes and algorithms with probabilistic performance guarantees. Often, a theoretical understanding of a problem’s structure plays an important role in the design of such algorithms. When the original problem is probably hard, a goal is to zero in on the boundary between the efficiently solvable special cases and the hard general case.
Computational Complexity
In addition to the study of sequential algorithms, we are interested in parallel computation especially since highly parallel machines are no longer just theoretical models. Complexity topics studied with respect to parallel computation include circuit complexity, upper bounds and models of computation. Another research topic is the interface between complexity theory and logic. The goal is to elaborate a theory of "feasibly constructive mathematics" where an efficient algorithm can be automatically generated from the proof of existence of a solution to a given problem. In this way, an algorithm and its correctness proof become essentially the same thing.
Approximation Algorithms
Most interesting optimization problems are NP-hard, and therefore it is unlikely that we can find optimal solutions for them efficiently. In many situations, finding a solution efficiently that is provably close to an optimal one is also acceptable. This is the main goal in this reasearch area: find provably good approximation solutions for the problems that are hard to solve exactly. These optimization problems arise from different areas, such as design of fault tolerant networks, routing problems, packing and covering problems, graph theory problems, and many more.
Combinatorial and Geometrical Algorithms
Another area of general interest is the development of algorithms, both sequential and parallel, in graph theory. Many of these problems arise from purely theoretical motivations, although specific problems currently under investigation have applications to scheduling, facilities location, and VLSI layout. We are also interested in the design and analysis of cost-effective and reliable communication networks. This involves solving many selection and enumeration problems over potentially large sets of structures. Current research activities in computational geometry are focused on problems arising in finite element mesh generation and on polygon covering problems.
Theory of Programming and Logic
Current research in this area includes work on automatic proof-checkers, program verification and equational logic as a programming language which includes equational logic programming and logic programming with equality and functions. This work involves declarative semantics to permit adequate expressive power and faithful operational semantics to allow efficient implementations.
For further information e-mail: .
