Academic History

• Education:
  • BA, 1979, Theatre, Computer Science (double major), University of Iowa
  • Ph.D., 1985, Information and Computer Science, Georgia Institute of Technology (Advisor: Kim N. King)
• Students
  • Vivek Gore (Formerly a professor at the University of Edinburgh, and now Vice President for Technology at CNSI.)
    • Thesis: Lower Bounds for Uniform Constant Depth Circuits, 1993.
  • Martin Strauss
    • Thesis: Measure in Feasible Complexity Classes, 1995.
  • Michal Koucký
    • Thesis: On Traversal Sequences, Exploration Sequences, and Completeness of Kolmogorov Random Strings , 2003.
  • Samir Datta
    • Thesis: Bounded Depth Arithmetic Circuits, 2004.
  • Detlef Ronneburger
    • Thesis: Kolmogorov Complexity and Derandomization, 2004.
  • Sambuddha Roy
    • IBM India Research Lab
    • Thesis: Complexity Theoretic Aspects of Planar Restrictions and Obliviousness, 2006.
• Employment
  • Professor, Dept. of Computer Science, Rutgers University (1997-present)
    • Department Chair (2006-present)
    • Director, Graduate Program in Computer Science (2006, and 1999-2003).
    • Member of DIMACS (1989-present)
    • Member of Graduate Faculty of Rutgers Mathematics Department (1993-present)
  • Associate Professor, Dept. of Computer Science, Rutgers University (1991-1997)
  • Assisstant Professor, Dept. of Computer Science, Rutgers University (1985-1991)
• Visiting Positions
  • 1989: Universität Würzburg
  • 1992-3: Princeton University
  • 1997: The Institute of Mathematical Sciences, Madras
  • 1997: Universität Tübingen
    
• Honors
  • Fellow of the ACM
  • ACM Distinguished Scientist
• Selected Invited Lectures
  • 10th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2008)
  • 3rd International Computer Science Symposium in Russia (CSR 2008) June 7-12, 2008, Moscow, Russia.
  • Computing: The Australasian Theory Symposium (CATS 2008), January 22-25, 2008, Wollongong, Australia.
  • Computability in Europe (CiE 2007), Special session on Complexity of Algorithms and Proofs June 18-23, 2007, Siena.
  • Conference on Logic, Computability and Randomness, January 10-13, 2007, Buenos Aires.
  • Symposium on Computational Complexity, Honoring Dr. Richard M. Karp, April 28, 2004, Philadelphia. (Presentation available on-line.)
  • 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003), Ouro Preto, Brazil, July 27-August 1, 2003.
  • Foundations of Computational Mathematics (FoCM 2002), semi-plenary speaker, Workshop on Complexity, Minneapolis, August 5-14, 2002.
  • 21st annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'01), Bangalore, India, December 13, 2001.
  • Summer Workshop on Computability, Complexity, and Computational Algebra, organized by the New Zealand Mathematical Research Institute, Kaikoura, New Zealand, January 7-14, 2000.
  • 17th International Conference of the Chilean Computer Science Society (SCCC '97), Viña del Mar, Chile, November 11, 1997.
  • 16th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'96), Hyderabad, India, December 18, 1996. (Presentation available on-line.)
  • 8th International Conference on Fundamentals of Computation Theory (FCT'90), Gosen, Germany, September 11, 1990.
  • SIGAL International Symposium on Algorithms, Tokyo, Japan, August 16, 1990.
• Professional Activities
  • Member of the Editorial Board: Computational Complexity (2006-present)
  • Member of the Editorial Board: ACM Transactions on Computation Theory (ToCT) (2007-present)
  • Member of Steering Committee, IEEE Structure in Complexity Theory Conference / IEEE Conference on Computational Complexity (2006-present and 1994-2001).
  • Scientific Board: Electronic Colloquium on Computational Complexity (1995-present).
  • Member, Chief Editorial Committee, DIMACS/AMS Book Series (2004-present).
  • Consulting Editor: Chicago Journal of Theoretical Computer Science (1998-present; editor since 1994).
  • Guest Editor, Special Issue of Computational Complexity on the 2004 IEEE Conference on Computational Complexity.
  • Chair, Steering Committee, IEEE Conference on Computational Complexity (1997-2000).
  • Editor, Computational Complexity Column, Bulletin of the European Association for Theoretical Computer Science (1997-2000).
  • Co-organizer, DIMACS Special Year on Logic and Algorithms (1995-1996).
  • Chair, program committee, 10th annual IEEE Structure in Complexity Theory Conference (1995).
  • Program Committee Membership
    • Computing: The Australasian Theory Symposium (CATS 2009), one of the conferences that constitute Australasian Computer Science Week 2009, Wellington, New Zealand.
    • 14h Annual International Computing and Combinatorics Conference (COCOON 2008). .
    • 39th ACM Symposium on Theory of Computing (STOC 2007).
    • 2nd Annual International Computer Science Symposium in Russia (CSR2007).
    • 12th Workshop on Logic, Language, Information and Computation (WoLLIC 2005).
    • 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005).
    • 19th Annual IEEE Conference on Computational Complexity (CCC 2004).
    • 2nd Annual IFIP Conference on Theoretical Computer Science (TCS 2002).
    • 7th Annual International Computing and Combinatorics Conference (COCOON 2001).
    • 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999).
    • XVII International Conference of the Chilean Computer Science Society (SCCC) (1997).
    • 15th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1995).
    • Annual IEEE Structure in Complexity Theory Conference (1989, 1993, 1995)
  • Workshop Co-organizer:
    • DIMACS-DIMATIA workshop: Algebraic Methods and Arithmetic Circuits (1999).
    • DIMACS workshop: Special Year on Logic and Algorithms -- One Year Later (1997).
    • Workshop on Structure and Complexity Theory, Schloss Dagstuhl, Germany (1996).
    • DIMACS Workshop on Structural Complexity and Cryptography (1990).
• Research Support
  • NSF Collaborative Research Grant, 2007--2010. See also the partner awards at Berkeley, Chicago, Connecticut, Dartmouth, Florida, Iowa State, Notre Dame, North Texas, Penn State, and Wyoming. The total award is $559,094. A web site describing the project can be found here.
  • NSF Grant, 2005--2008.
  • NSF Grant, 2001--2004.
  • NSF Grant, 1998--2001.
  • Deutsche Forschungsgemeinschaft Grant TU 7/117-1, 1997.
  • NSF Grant, 1995--1998.
  • NSF Grant, 1992--1995.
  • NSF Grant, 1990--1992.
  • NSF Research Initiation Grant, 1988--1990.
• Publications
• Miscellaneous
  • A nice comment from a former undergraduate.
  • And another.