Research InterestsMy main interests are in the areas of combinatorics, optimization and complexity theory. Combinatorics: A large number of combinatorial theorems claim the existance of a structure yet the proof does not explicitly exhibit this structure. One example is the work of Robertson and Seymour on graph minors which establishes the existence of polynomial algorithms for a large number of problems yet there seems to be no direct method of obtaining these algorithms from the proof of existence. I am looking at a number of aspects of the graph minors work to gauge its constructive content.
Optimization: In operations research, scheduling problems arise from both theoretical and practical considerations. Past work has concentrated on finding exact solutions to such problems. I am interested in applying the theory of randomized algorithms to deliver very fast solutions which exhibit good performance ratios.
Complexity Theory: One of the most fundamental questions in computer science deals with the resources required to solve a problem. The goal is to obtain tight upper and lower bounds on these resources. However, because algorithms can work in novel ways, computing good lower bounds had turned out to be difficult for most problems. More recent work has focused on the study of parallel complexity theory. From a theoretical point of view the trade-off between the number of processors and execution time seems to depend on the problem being solved. For some problems, parallel computation does not seem to yield algorithms significantly faster than sequential computation. I am interested in trying to determine which problems have fast parallel algorithms with respect to a number of different models of parallel machines.
Suggestions for additions?