Computational Complexity Theory
The current research focuses on the following inter-related research areas:
Complexity and Approximability of Combinatorial Problems
We are investigating the complexity of decision, counting and approximate optimization of combinatorial problems. The main goal of this research is to identify uniform proof techniques that can be used to demonstrate the hardness/easiness of basic combinatorial problems for different complexity classes. Two main areas of research currently investigated are (i) approximability of NP- PSPACE- and EXPTIME-hard optimization problems and (ii) complexity and approximability of generalized satisfiability problems. In this line of work I have been investigating the complexity and approximability of problems specified using succinct specifications. The research is likely to yield a better understanding of how the instance representation and the structure of instances affect the overall computational complexity of combinatorial problems. The specifications we consider are motivated by large scale hierarchical system design as well as temporally varying phenomena.
Computational Complexity Theory
Perhaps the most important task of Theoretical Computer Science is to offer insights on the reasons that make an instance of a combinatorial problem "hard". Recently it has been shown experimentally that the "hardest" such instances are located near points where a phase transition takes place.
Our work in this area has two long-term objectives:
- to offer rigorous counterparts to results that were observed experimentally in the Artificial Intelligence literature
- to ellucidate the connection between computational complexity and the existence of a phase transition.
|
