Eric Allender

Professor
Department of Computer Science
Rutgers, the State University of NJ
110 Frelinghuysen Road
Piscataway, NJ 08854-8019
USA
Phone: (732) 445-3629
FAX: (732) 445-0537
Email: allender@cs.rutgers.edu
Office: Hill 442

Academic Information

Academic History
· Education:
o BA, 1979, Theatre, Computer Science (double major), University of Iowa
o Ph.D., 1985, Information and Computer Science, Georgia Institute of Technology (Advisor: Kim N. King)
· Students
o 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.
o Martin Strauss
§ Thesis: Measure in Feasible Complexity Classes, 1995.
o Michal Koucký
§ (See also pages at the Dept. of Mathematical Logic, Numerical Algebra and Graph Theory of the Academy of Sciences of the Czech Republic, at CWI in Amsterdam and at McGill University)
§ Thesis: On Traversal Sequences, Exploration Sequences, and Completeness of Kolmogorov Random Strings , 2003.
o Samir Datta
§ (See also page at WINLAB)
§ Thesis: Bounded Depth Arithmetic Circuits, 2004.
o Detlef Ronneburger
§ (See also page at York College, CUNY.)
§ Thesis: Kolmogorov Complexity and Derandomization, 2004.
o Sambuddha Roy
· Visiting Positions
o 1989: Universität Würzburg
o 1992-3: Princeton University
o 1997: The Institute of Mathematical Sciences, Madras
o 1997: Universität Tübingen
· Selected Invited Lectures
o Symposium on Computational Complexity, Honoring Dr. Richard M. Karp, April 28, 2004, Philadelphia. (Presentation available on-line.)
o 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003), Ouro Preto, Brazil, July 27-August 1, 2003.
o Foundations of Computational Mathematics (FoCM 2002), semi-plenary speaker, Workshop on Complexity, Minneapolis, August 5-14, 2002.
o 21st annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'01), Bangalore, India, December 13, 2001.
o Summer Workshop on Computability, Complexity, and Computational Algebra, organized by the New Zealand Mathematical Research Institute, Kaikoura, New Zealand, January 7-14, 2000.
o 17th International Conference of the Chilean Computer Science Society (SCCC '97), Viña del Mar, Chile, November 11, 1997.
o 16th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'96), Hyderabad, India, December 18, 1996. (Presentation available on-line.)
o 8th International Conference on Fundamentals of Computation Theory (FCT'90), Gosen, Germany, September 11, 1990.
o SIGAL International Symposium on Algorithms, Tokyo, Japan, August 16, 1990.
· Professional Activities
o Scientific Board: Electronic Colloquium on Computational Complexity (1995-present).
o Consulting Editor: Chicago Journal of Theoretical Computer Science (1998-present; editor since 1994).
o Editor, Special Issue of Computational Complexity on the 2004 IEEE Conference on Computational Complexity.
o Director, Rutgers Graduate Program in Computer Science (1999-2003).
o Chair, Steering Committee, IEEE Computational Complexity Theory Conference (1997-2000).
o Editor, Computational Complexity Column, Bulletin of the European Association for Theoretical Computer Science (1997-2000).
o Co-organizer, DIMACS Special Year on Logic and Algorithms (1995-1996).
o Chair, program committee, 10th annual IEEE Structure in Complexity Theory Conference (1995).
o Member of Steering Committee, IEEE Structure in Complexity Theory Conference / IEEE Conference on Computational Complexity, 1994-2001.
o Program Committee Membership
§ 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)
o 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
o NSF Grant, 2001--2004.
o NSF Grant, 1998--2001.
o Deutsche Forschungsgemeinschaft Grant TU 7/117-1, 1997.
o NSF Grant, 1995--1998.
o NSF Grant, 1992--1995.
o NSF Grant, 1990--1992.
o NSF Research Initiation Grant, 1988--1990.
· Miscellaneous
o A nice comment from a former undergraduate.

Research Publications

Research Publications by Eric Allender
Complete List of Research Publications
All of my papers are available on-line.
Papers organized by Research Topic
Follow the links below to find papers that I have written, categorized according to my research interests. Some papers are listed in more than one category.
Circuit Complexity
Structure of Complexity Classes and Complete Sets; Reducibilities
Probabilistic Computation and Derandomization
Lower Bounds
Relations among Complexity Classes
Logarithmic-Space-Bounded Complexity Classes
Kolmogorov Complexity
Complexity of Markov Decision Process Problems
Resource-Bounded Measure
Expository Articles and Surveys

Complexity Theory Lecture Notes
There are two graduate-level courses in complexity theory that I have taught here at Rutgers. Notes that were prepared for some of the material covered in those courses are available for your reading pleasure.
198:538 -- Complexity of Computation
· Levin's Lower Bound Theorem (These notes present a lovely theorem that should be in all textbooks but isn't. Everyone knows Blum's "speed-up theorem" that shows that there are certain problems that have nothing at all like an optimal algorithm. At first glance, this might indicate that some problems have no tight lower bound on their complexity. However this result of Levin's shows that every computable function does have a tight lower bound.)
198:540 -- Combinatorial Methods in Complexity Theory
· Notes1 (Introduction. Proof of the Parity lower bound for constant-depth circuits, assuming the switching lemma.)
· Notes2 (Start of the proof of the switching lemma, using the argument based on Kolmogorov complexity.)
· Notes3 (End of the proof of the switching lemma.)
· Notes4 (Bounds on the number of inputs on which an AC^0 circuit can compute parity correctly. Depth-reduction for (probabilistic) AC^0 circuits with mod gates.)
· Notes5 (Constructing deterministic circuits with adequate performance from probabilistic circuits.)
· Notes6 (AC^0 with mod p gates can't compute mod q.)
· Notes7 (Normal forms for ACC circuits.)
· Notes8 (ACC can be done by depth 2 probabilistic circuits with a symmetric gate at the root.)
· Notes9 (Valiant-Vazirani construction to reduce the number of probabilistic bits, allowing the ACC result to go through with deterministic circuits.)
· Notes10 (The "fusion method" for proving circuit lower bounds.)
· Notes11 (Application of the "fusion method" to prove a lower bound on monotone circuit size required to compute 3-clique.)
· Notes12 (The general lower bound for monotone circuit size required to compute k-clique.)
· Notes13 (Resolution-based theorem proving, Craig interpolation, related results.)
· Notes14 (Relationships between resolution refutation length and (monotone) circuit size.)
· Notes15 (An introduction to probabilistically-checkable proofs. There are no further class notes on PCP; refer instead to the text by Arora available through ECCC.)
Other Excellent Sets of Notes
· For the past several years, McGill University and Université de Montréal have run a series of workshops on complexity theory at McGill's Bellairs Research Center in Barbados. Recently, they have started producing detailed notes of the main lectures there. The notes that have appeared thus far are:
Lectures on the Fusion Method and Derandomization (lectures by Avi Wigderson).
Lectures on Proof Theory (lectures by Sam Buss).
Around the PCP Theorem (lectures by Sanjeev Arora)
· The DIMACS Special Year on Logic and Algorithms generated a set of notes from the tutorials held in August, 1995. There are notes on Finite Model Theory, Proof Complexity, and Computer-Aided Verification.

Professional Activities
· Program Committee: 12th Workshop on Logic, Language, Information and Computation (WoLLIC 2005).
· Program Committee: 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005).
· Former Chair: IEEE Conference on Computational Complexity
· Scientific Board: Electronic Colloquium on Computational Complexity
· Consulting Editor: Chicago Journal of Theoretical Computer Science
(See also highly unprofessional activities.)
Classes, Office Hours, Etc.
· I am helping Prof. S. Muthukrishnan organize the weekly DIMACS CS-Theory Seminar.
· In Spring, 2005, I will be teaching 198:538 (Complexity of Computation)
· Click here for current Office Hours.
· Click here to see my picture.
Related Links at Rutgers
· Theoretical Computer Science at Rutgers
· Department of Mathematics
· DIMACS
· AAUP (American Association of University Professors)
· Rutgers Info System Search Facility