|
Computational Complexity Theory
The current
research focuses on the following inter-related reseach 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.
- Phase Transitions
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.
Back to Top 
|
|
|
