Steven Lindell

Professor of Computer Science

Biography

I received my B.A. and M.A. in Mathematics at UCLA, and went on to receive a Ph.D. in theoretical Computer Science at UCLA under the supervision of Sheila Greibach and Yiannis Moschovakis (mathematical logic) in 1987. Since then I have been coordinator of the Computer Science program at Haverford College, which offers a minor along with a concentration for Mathematics and Physics majors. Although we have limited resources, students can petition to pursue an independent major in Computer Science. The courses we offer are geared toward preparing students for graduate study by emphasizing the foundations of the subject.

Education

B.A., M.A., and Ph.D., University of California, Los Angeles

Research

I work on the foundations of theoretical computer science, in an area of logic known as finite model theory and the related field of descriptive complexity. I study the logical definability of complexity classes given by models of computation whose resources are bounded by mathematical (or physical) limits. My papers are often concerned with elementary (first-order) and inductive (fixed-point) definability on finite structures, in as much as these logics shed light on fundamental questions in the complexity of computation. More recently, I have been interested in logically characterizing the fundamental physical limitations of mechanical computing devices, and related general issues in the philosophical foundations of logic, information and computation. This work is highly abstract, but may be of substantial practical importance when it becomes impossible to make substantial technological improvements to computers.