The goal of  this project is to study the  intrinsic computational  complexity of  problems.  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.
   

Representative Publications:
 

"Theory of Periodically Specified Problems: Complexity and Approximability,"
M. V. Marathe, H. B. Hunt III, D. J. Rosenkrantz, and  R. E. Stearns, in Proc.13th IEEE Conference on Computational Complexity, Buffalo, NY, (June 1998).

"The Complexity of Planar Counting Problems,"
H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns, in SIAM J. Computing, 27(4),  pp. 1142--1167 (August 1998).  

"Complexity of Hierarchically and 1-Dimensional Periodically Specified Problems I: Hardness Results,"
M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan, in AMS-DIMACS Volume Series on  Discrete Mathematics and Theoretical Computer  Science;  Workshop on Satisfiability Problem: Theory and Application, (35), pp. 225--259 (Nov. 1996).

"Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems,''
M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan, in SIAM J. Computing, 27(5), pp. 1237--1261, Oct. 1998.  A Preliminary version titled  "Approximation Schemes for PSPACE-Complete Problems  for Succinct Specifications,"  appears in Proc. 26th Annual ACM Symposium on the Theory of Computing (STOC), Montreal, Canada, pp. 468--478 (May 1994).

"The Phase Transition in Random Horn Satisfiability and its Algorithmic Implications," G. Istrate, to appear in  Random Structures and Algorithms .

"Algorithmic Implications of  Phase Transitions," G. Istrate, in Proceedings of the 15'th annual Conference on Computational Complexity (CCC'00).

"On the Satisfiability of Random k-Horn Formulas," to appear in the proceedings of the DIMACS - Dimaitic Workshop on Graphs, Morphisms and Statistical Physics, P. Winkler et. al. (editors)

"The Phase Transition in 1-in-k SAT and NAE 3-SAT," D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore, in Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (SODA'01).

Back to Top