Harry B. Hunt III Ph.D., Cornell University

Computer Science Department
University at Albany
Albany, NY 12222
(518) 442-4276
(518) 442-5638 (FAX)

Personal Statement of Research
Intuitively, the complexity of a problem is the amount of some resource, e.g. time, space, size of circuit, number of processors, etc., required to solve it. A problem is "hard" if its solution requires a large amount of the resource. It is "easy" if its solution requires a small amount of the resource. My research centers upon finding answers to the questions --

1. What makes particular problems "hard"?
2. What makes other problems "easy"?

I am interested in finding answers, for questions 1 and 2 for problems for the various structures studied in computer science and applied mathematics. Structures under investigation include graphs and hypergraphs, abstract algebraic structures (e.g., lattices, semi-lattices, rings, semi-rings), discrete and finite dynamical systems, networks of communicating processes, and combinatorial games.
Research is also underway in the areas of combinatorial and sequential logic, database systems, program development and code optimization in high- performance scientific programming, simulation science, and combinatorial optimization and approximation. Much of this work is joint with coworkers here and/or at Los Alamos National Laboratory, Los Alamo, New mexico.
Selected Publications
  1. R.E. Stearns and H.B. Hunt III
    "Exploiting structure in quantified formulas"
    Journal of Algorithms 43, pp.220-263

  2. L.R. Mullin, D.J. Rosenkrantz, H.B. Hunt III and X. Luo
    "Efficient radar processing via array- and pointer-algebras"
    1st Workshop on Optimization for DSP and Embedded Systems (ODES'03), San Francisco, Ca., March 2003

  3. C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns
    "Predecessor and permutation existence problems for sequential dynamic systems"
    Proc. International Conf. on Discrete Models for Complex Systems (DM-CS-2003), Lyons, France, June 2003, pp.69-80

  4. R.E. Stearns and H.B. Hunt III
    "Resource Bounds and Subproblem Independance"
    Theoretical Computing Systems 38, pp.731-761, 2005

  5. H.B. Hunt III, M.V. Marathe, D.J. Rosenkrantz and R.E. Stearns
    "Towards a predictive computational complexity theory for periodically specified problems: a survey"
    Computational Complexity and Statistical Physics, A.G.Percus, G.Istrate and C.Moore (Editors), Oxford University Press, N.Y., pp.285-318, 2006

  6. D.J. Rosenkrantz, L.R. Mullin and H.B. Hunt III
    "On minimizing materializations of array-valued temporaries"
    to appear in ACM TOPLAS

  7. C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns and M. Thakur
    "Computational complexity of analyzing dynamic reliability of interdependant infrastructures"
    to be presented at 3rd International Conference on Critical Infrastructures (CRIS06)