Skip to content Skip to navigation

Eric Allender

Distinguished Professor
Email: 
Phone: 
(848) 445-7296
Office: 
Hill 442
Research Area: 
Computational Complexity Theory
Kolmogorov Complexity
Address: 
Dept. of Computer Science
Rutgers University
110 Frelinghuysen Road
Piscataway, NJ 08854, USA
Biography: 

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.

Personal News: 
Grant Awards: 
Publications: 
Displaying 1 - 3 of 3

Eric Allender, Anna Gal, and Ian Mertz

Computational Complexity
October, 2016

Eric Allender, Dhiraj Holden, and Valentine Kabanets

Computational Complexity
February, 2016

Eric Allender and Bireswar Das

August, 2014
  • Best paper award, MFCS 2015
Classes Taught: 
  • 198:205 Introduction to Discrete Structures I
  • 198:206 Introduction to Discrete Structures II
  • 198:452 Formal Languages and Automata Theory
  • 198:509 Foundations of Computer Science
  • 198:538 Complexity of Computation
  • 198:540 Combinatorial Methods in Complexity Theory
Student, PostDocs, & Visitors: 

Ph.D. Student: Erick Chastain

Alumni: 

Doctoral advisees:

Undergraduate Research Advisees:

  • Ian Mertz (2012-2016; NSF REU 2014)
  • Michael Rudow (DIMACS REU 2016)
  • Asa Goodwillie (DIMACS REU 2015)
  • Dhiraj Holden (NSF REU 2014)
  • Sam Hopkins (DIMACS REU 2011)
  • Chris Calabro (Henry Rutgers Thesis, 2000)

Research Projects

The goal of this activity is to understand the structure of complexity classes. Complexity...