Education

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

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.  After graduating, I began the Computer Science program at Haverford College, which now offers a full CS major. 

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.