|
Representative Publications
Computational Complexity Theory
"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).
|
|
