1948 – 2004
Larry Stockmeyer (1948-2004) was an American computer scientist known for foundational contributions to computational complexity theory. He is best known for introducing the polynomial hierarchy and for proving lower bounds on the complexity of decision problems, including the influential result on the complexity of the first-order theory of real addition.
Introduced the polynomial hierarchy in computational complexity theory
Proved lower bounds for the first-order theory of real addition (Stockmeyer-Meyer theorem)
Contributed foundational results on the complexity of regular expression equivalence
Advanced understanding of the relationship between logic and computational resources
IBM Fellow and influential researcher at IBM Almaden Research Center