The goal of this activity is to understand the structure of complexity classes. Complexity...
I work in Computational Complexity Theory, with particular emphasis on Circuit Complexity, Complexity Classes, and connections between computational complexity and Kolmogorov Complexity.
I received a B.A. from the University of Iowa in 1979, majoring in Computer Science and Theater. Then I spent a year doing hotel and restaurant work in Germany, to see a bit of the world, before starting grad school at Georgia Tech in 1980. I received my PhD in 1985, and I've been at Rutgers ever since, except for brief visiting positions over the years at Würzburg, Princeton, The Institute of Mathematical Sciences in Chennai, India,Tübingen, Victoria University in Wellington, New Zealand, Macquarrie University in Sydney, Tsinghua, San Diego, and the Santa Fe Institute. During the 2009/2010 academic year,I was a Fulbright Fellow in South Africa (University of Cape Town, and UNISA in Pretoria). I served as CS department chair here at Rutgers from 2006 to 2009.
I currently serve as the Editor-In-Chief of ACM Transactions on Computation Theory, and I also serve on the editorial boards of Computability (the journal of the association CiE), and the Chicago Journal of Theoretical Computer Science. I am the treasurer of the Computational Complexity Foundation.
Ph.D. Student: Erick Chastain
Undergraduate Research Advisees: