Complete List of Research Publications by Eric Allender

Note: Journal and conference publications from 2014 on are also archived at the Scholarly Open Access at Rutgers site.

Comment on “SAT requires exhaustive search”
(with Ryan Williams), Frontiers of Computer Science 20 (2026).

Kolmogorov Complexity Characterizes Statistical Zero Knowledge,
(with Shuichi Hirahara and Harsha Tirumala), ACM Transactions on Computation Theory (ToCT) 18,2 (2026) 14:1-14:29. An earlier version appeared in Proc. 14th Innovations in Theoretical Computer Science (ITCS'23) 2023, Leibniz International Proceedings in Informatics (LIPIcs) 251, pp. 3:1--3:19. There is a video of a Princeton Theory Lunch talk on this paper (Sept. 30, 2022). It's a blackboard talk, and the writing on the blackboard is hard to read in the video.

Robustness for Space-Bounded Statistical Zero Knowledge
(with Jacob Gray, Saachi Mutreja, Harsha Tirumala, and Pengxiang Wang), ACM Transactions on Computation Theory (ToCT), 17,1 (2025) 3:1-3:27. , An earlier version appeared in Proc. International Workshop on Randomization and Computation (RANDOM 2023), Leibniz International Proceedings in Informatics (LIPIcs) 275, pp. 56:1--56:21. The soundness argument for Theorem 29 in the published version is not sufficiently rigorous. For a more convincing argument, see the most recent revision of ECCC Report TR22-138,.

Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!) ,
Guest Piece for the Complexity Theory Column, edited by Lane Hemaspaandra, SIGACT NEWS 54 March, 2023, pp. 63--81. UPDATE, July, 2024: Alexey Milovanov has presented a solution to Open Problem 10, showing that there is a Universal Turing Machine defining Kolmogorov complexity, such that the Halting Problem (and thus every computably-enumerable set) is poly-time reducible to the Kolmogorov random strings. UPDATE, February, 2026: Alexey Milovanov has solved the other half of Open Problem 10, showing that there is a Universal Turing Machine defining plain Kolmogorov complexity, such that the Halting Problem is NOT poly-time reducible to the Kolmogorov random strings. UPDATE, August, 2026: Together with a co-author, Alexander Shekhovtsov has presented solutions to Open Question 3 (by characterizing ACC0 in terms of small genus) and part of Open Question 9 (by showing, nonconstructively, the existence of an irrational algebraic number that is not in AC0).

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs ,
(with Nikhil Balaji, Samir Datta, and Rameshwar Pratap) Computability (The Journal of the Association Computability in Europe) 12 (2023) pp. 145-173. Some of this work appeared in preliminary form as Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs,
(with Nikhil Balaji and Samir Datta), in Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), Lecture Notes in Computer Science8635, pp. 13-24, 2014.

Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity ,
(with John Gouwar, Shuichi Hirahara, and Caleb Robelle), Theoretical Computer Science 940(B), 2023, 206-224; special issue for Péter Gács. (An earlier version appeared in preliminary form in Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs) 212, pp. 54:1--54:17.) See also ECCC Report TR21-010, 2021.

Depth-First Search in Directed Planar Graphs, Revisited,
(with Archit Chauhan and Samir Datta), Acta Informatica, 59 (2022) 289-319; special issue for Klaus-Jörn Lange. (An earlier version appeared in preliminary form in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS '21), Leibniz International Proceedings in Informatics (LIPIcs) 202, pp. 7:1 -- 7:22.

Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization,
New Zealand Journal of Mathematics 52 (2021), pp. 585-604; special issue on Vaughan Jones. An earlier version appeared as The New Complexity Landscape around Circuit Minimization, Proc. 14th International Conference on Language and Automata Theory and Applications (LATA 2020), Lecture Notes in Computer Science 12038, pp. 3-16.

One-way Functions and a Conditional Variant of MKTP ,
(with Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich ), Proc. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs) 213, pp. 7:1--7:19. See also ECCC Report TR21-009, 2021.

The Non-Hardness of Approximating Circuit Size,
(with Rahul Ilango, and Neekon Vafa), Theory of Computing Systems, 65,3 (2021) 559-578. An earlier version appeared x in Proc. 14th International Computer Science Symposium in Russia (CSR 2019), Lecture Notes in Computer Science 11532, pp. 13-24.

A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity,
(with Azucena Garvìa Bosshard and Amulya Musipatla), ECCC Report TR20-158, 2020.

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity,
in Complexity and Approximation, in Memory of Ker-I Ko, edited by Ding-Zhu Du and Jie Wang, Lecture Notes in Computer Science 12000, pp. 8-18, Springer-Verlag, 2020.

Syntactic Separation of Subset Satisfiability Problems,
(with Martin Farach-Colton and Meng-Tsung Tsai), Proc. 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2019), Leibniz International Proceedings in Informatics (LIPIcs) 145, pp. 16:1--16:23.

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems,
(with Shuichi Hirahara), ACM Transactions on Computation Theory (ToCT), 11,4 (2019) 27:1-27:27. An earlier version appeared in Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS '17), Leibniz International Proceedings in Informatics (LIPIcs) 83, pp. 54:1--54:14.

Better Complexity Bounds for Cost Register Automata,
(with Andreas Krebs and Pierre McKenzie ), Theory of Computing Systems 63(3), 2019, 367-385. An earlier version appeared in Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS '17), Leibniz International Proceedings in Informatics (LIPIcs) 83, pp. 24:1--24:14.

Complexity of Regular Functions,
(with Ian Mertz), Journal of Computer and System Sciences 104, 2019, 5-16. (Special issue on LATA '15.) An earlier version appeared in Proc. 9th International Conference on Language and Automata Theory and Applications (LATA '15), Lecture Notes in Computer Science 8977, pp. 449-460, 2015.

Minimum Circuit Size, Graph Isomorphism and Related Problems,
(with Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan), SIAM J. Comp., Vol. 47(4), 2018, 1339-1372. An earlier version appeared in Proc. 9th Innovations in Theoretical Computer Science (ITCS '18), Leibniz International Proceedings in Informatics (LIPIcs) 94 pp. 20:1--20:20. (See the Presentation at the Simons Institute.)

A note on Graph Automorphism and Smart Reductions,
(with Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan), ECCC Technical Report TR15-162, 2018.

Zero Knowledge and Circuit Minimization,
(with Bireswar Das), Information and Computation, 256 (2017) 2-8. (Special issue on MFCS 2014.) An earlier version appeared in Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS '14), Lecture Notes in Computer Science 8635, pp. 25-32, 2014. (Presentation available on-line.)

The Complexity of Complexity,
in Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer-Verlag, 2017, Lecture Notes in Computer Science 10010, pp. 79--94, 2017.

The Minimum Oracle Circuit Size Problem,
(with Dhiraj Holden and Valentine Kabanets), Computational Complexity 26 (2017) 469-496. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics (LIPIcs) 30, 2015, pp. 21-33.

Dual VP Classes,
(with Anna Gál and Ian Mertz), Computational Complexity 26 (2017) 583-625. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS '15), Lecture Notes in Computer Science 9235, pp. 14-25, 2015. (Presentation available on-line.) (A companion paper is Arithmetic Circuit Classes over Zm (with Asa Goodwillie), ECCC Technical Report TR15-145, 2015.)

On the Power of Algebraic Branching Programs of Width Two,
(with Fengming Wang), Computational Complexity 25 (2016) 217-253. Springer provides free read-only access to this publication. An earlier version appeared in Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), 2011, Lecture Notes in Computer Science 6755, pp. 736-747.

Investigations Concerning the Structure of Complete Sets,
in Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Progress in Computer Science and Applied Logic vol. 26, 2014, pp. 23-35.

Reductions to the set of random strings: The resource-bounded case,
(with Harry Buhrman, Luke Friedman, Bruno Loff), Logical Methods in Computer Science 10 (3:5) 2014, pp. 1-18. (Special issue on The Turing Centenary Conference: CiE 2012). An earlier version appeared in Proc. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS '12), 2012, Lecture Notes in Computer Science 7464, pp. 88-99, 2012.

Width-parameterized SAT: time-space tradeoffs,
(with Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, and Bangsheng Tang),
Theory of Computing 10(12), 2014, 297-339.

Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata,
(with Klaus-Jörn Lange). Theory of Computing 10(8), 2014, 199-215. An earlier version appeared in Proc. 25th Annual IEEE Conference on Computational Complexity (CCC), 2010, pp. 172-180.

Complexity Theory,
(with Michael Loui and Kenneth Regan), in the Computing Handbook, Third Edition, Volume 1 ed. Allen Tucker, Teofilo Gonzalez, Heikki Topi, and Jorge Diaz-Herrera, 2014, Chapman and Hall/CRC Press. An earlier version of this work appeared in CRC Computer Science Handbook, Second Edition, ed. Allen B. Tucker, Jr., 2004, CRC Press, pp. 5-1 - 5-30.

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic,
(with George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret),
Chicago Journal of Theoretical Computer Science, 2013, article 5.

Limits on the Computational Power of Random Strings,
(with Luke Friedman and William Gasarch), Information and Computation, 222 (2013) 80-92. (Special issue on ICALP 2011). An earlier version appeared in Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), 2011, Lecture Notes in Computer Science 6755, pp. 293-304. (A companion paper is Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions (with Luke Friedman and William Gasarch), ECCC Technical Report TR10-138, 2010.)

Curiouser and Curiouser: The Link between Incompressibility and Complexity,
in Proc. Computability in Europe: (CiE 2012), Lecture Notes in Computer Science 7318, pp. 11-16, 2012.

Uniform Derandomization from Pathetic Lower Bounds,
(with V Arvind, Rahul Santhanam and Fengming Wang), . Philosophical Transactions of the Royal Society, Series A, 370, 2012, 3512-3535. Special issue on the Turing Centenary. See also the Comment on ECCC. An earlier version appeared in Proc. 14th International Workshop on Randomization and Computation (RANDOM/APPROX 2010), Lecture Notes in Computer Science 6302, pp. 380-393, 2010.

Avoiding Simplicity is Complex, (with Holger Spakowski),
Theory of Computing Systems 51, 2012, 282-296. Special issue on CiE 2010. Springer provides free read-only access to this publication. An earlier version appeared in Proc. Computability in Europe: Programs, Proofs, Processes (CiE 2010), Lecture Notes in Computer Science 6158, pp. 1-10, 2010.

Randomness as Circuit Complexity (and the Connection to Pseudorandomness),
in Randomness through Computation: Some answers, more questions, edited by Hector Zenil, World Scientific Press, 2011, pp. 267-274.

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory,
(with Michal Koucký, Detlef Ronneburger, and Sambuddha Roy), Journal of Computer and System Sciences 77, 2011, 14-40. (Some of this material appeared in preliminary form in the paper Derandomization and Distinguishing Complexity, Proc. 18th Annual IEEE Conference on Computational Complexity (CCC), 2003, pp. 209-220.)

New Surprises from Self-Reducibility, in Programs, Proofs, Processes, (ed. F. Ferreira, H. Guerra, E. Mayordomo, and J. Rasga), Abstract and Handout Booklet,
6th Conference on Computability in Europe (CiE 2010), Centre for Applied Mathematics and Information Technology, Dept. of Mathematics, University of Azores, pp. 1--5, 2010.

Amplifying Lower Bounds by Means of Self-Reducibility,
(with Michal Koucký), Journal of the ACM 57,3 (2010) 14:1 - 14:36. An earlier version appeared in Proc. 23rd Annual IEEE Conference on Computational Complexity (CCC), 2008, pp. 31--40.

Three chapters: Chapter 22: Complexity Classes, Chapter 23: Reducibility and Completeness, and Chapter 24: Other Complexity Classes and Measures,
(with Michael Loui and Kenneth Regan), in Algorithms and Theory of Computation Handbook, Second Edition, Volume 1: General Concepts and Techniques , ed. M. Atallah and M. Blanton, 2009, Chapman and Hall/CRC Applied Algorithms and Data Structures Series, CRC Press. (Earlier versions of this work appeared as Chapters 27-29 in the 1999 edition, edited by M. Atallah.)

A Status Report on the P versus NP Question ,
in Advances in Computers Vol. 77, Academic Press, 2009, pp. 118-147. (Marvin Zelkowitz, editor).

Computational Complexity Theory,
in Encyclopedia of Computer Science and Engineering, Volume 1, Wiley Interscience, 2009, pp. 500-506. (Benjamin Wah, editor in chief).

Planar and Grid Graph Reachability Problems,
(with David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta and Sambuddha Roy), Theory of Computing Systems, Vol. 45, 2009, 675-723. Special issue devoted to CiE 2007. Springer provides free read-only access to this publication. (This material appeared in preliminary form in the papers The Directed Planar Reachability Problem, Proc. 25th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2005, Lecture Notes in Computer Science 3821, pp. 238-249, and Grid Graph Reachability Problems, Proc. 21st Annual IEEE Conference on Computational Complexity (CCC), 2006, pp. 299--313. See also Reachability Problems: An Update, Proc. Computation and Logic in the Real World, 3rd Conference of Computability in Europe, (CiE 2007), Lecture Notes in Computer Science 4497, 2007, pp. 25-27.)

On the Complexity of Numerical Analysis,
(with Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen), SIAM J. Comp. Vol. 38, 2009, 1987-2006. An earlier version appeared in Proc. 21st Annual IEEE Conference on Computational Complexity (CCC), 2006, pp. 331--339.

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem,
(with Michael Bauland, Neil Immerman, Henning Schnoor, and Heribert Vollmer), Journal of Computer and System Sciences 75, 2009, 245-254. An earlier version appeared in Proc. 30th International Symposium on Mathematical Foundations of Computer Science (MFCS '05), 2005, Lecture Notes in Computer Science 3618, pp. 71-82.

Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table,
(with Lisa Hellerstein, Paul M. McCabe, Toniann Pitassi, and Michael Saks), SIAM J. Comp. Vol. 38, 2008, 63-84. An earlier version appeared in Proc. 21st Annual IEEE Conference on Computational Complexity (CCC), 2006, pp. 237--251. NOTE:The bound reported in Lemma 4.3 is not correct, although when the correct bound is used, the theorem still holds. See the comment on the ECCC version of this paper for more details.

Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds,
in Proc. 10th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2008), 2008, pp. 7-13.

Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds,
in Proc. 3rd International Computer Science Symposium in Russia (CSR 2008), Lecture Notes in Computer Science 5010, pp. 3-10, 2008.

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?,
(with Harry Buhrman and Michal Koucký), Annals of Pure and Applied Logic 138 (2006) 2-19. An earlier version appeared in Proc. 21st International Symposium on Theoretical Aspects of Computer Science (STACS), 2004, Lecture Notes in Computer Science 2996, pp. 584-595.

Power from Random Strings,
(with Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger), SIAM J. Comp. Vol. 35, 2006, 1467-1493. An earlier version appeared in FOCS 2002, pp. 669-678. See also A Comment Regarding KT and Circuit Size.

NL-printable sets and Nondeterministic Kolmogorov Complexity,
Theoretical Computer Science Vol. 355, 2006 127-138. Special issue on WOLLIC 2003. (An earlier version appeared as an invited paper in Proc. 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003) , 2003, pp. 6-20.)

Topology inside NC^1,
(with Samir Datta and Sambuddha Roy), Proc. 20th Annual IEEE Conference on Computational Complexity (CCC), 2005, pp. 298-307. Note: The proof of Theorem 6 is incorrect, and it is not known if Theorem 6 is true. See this paper for a discussion of this point.

Arithmetic Circuits and Counting Complexity Classes,
in Complexity of Computations and Proofs, edited by Jan Krajíček, Quaderni di Matematica Vol. 13, Seconda Universita di Napoli, 2004, pp. 33-72. An earlier version, called Making Computation Count: Arithmetic Circuits in the Nineties appeared in the Complexity Theory Column, edited by Lane Hemaspaandra, SIGACT NEWS 28, 4 (December, 1997) pp. 2-15.

The Division Breakthroughs,
in Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 1: Algorithms and Complexity, edited by G. Paun, G. Rozenberg, and A. Salomaa, World Scientific Press, 2004, pp. 147-164. An earlier version appeared in The Computational Complexity Column, Bulletin of the EATCS, volume 74, June, 2001, pp. 61-77.

The Complexity of Planarity Testing,
(with Meena Mahajan). Information and Computation 189 (2004) 117-134. An earlier version appeared in in Proc. 17th International Symposium on Theoretical Aspects of Computer Science (STACS), 2000, Lecture Notes in Computer Science 1770, pp. 87-98.

Complexity of some Arithmetic Problems for Binary Polynomials,
(with Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks and Igor Shparlinski). Computational Complexity 12 (2003) 23-47. Springer provides free read-only access to this publication.

Arithmetic Complexity, Kleene Closure, and Formal Power Series,
(with V Arvind and Meena Mahajan), Theory of Computing Systems, 36 (2003) 303-328. Also see a Corrigendum, which appeared as Theory of Computing Systems 53 (2013) 503-506. Springer provides free read-only access to this publication, and to the corrigendum.

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics,
(with Sanjeev Arora, Michael Kearns, Cristopher Moore, and Alexander Russell), in Proc. 16th Annual Conference on Neural Information Processing Systems (NIPS 2002), MIT Press, 2003, pp. 431--437.

Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication,
(with William Hesse and David A. Mix Barrington), Journal of Computer and System Sciences 65 (2002) 695-716. Special issue on CCC 2001. Also see a corrigendum, which appeared as J. Computer and System Sciences 80 (2014) 496--497. An earlier version appeared as Uniform Circuits for Division: Consequences and Problems, Proc. 16th Annual IEEE Conference on Computational Complexity (CCC), 2001, pp. 150-159.

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity,
Invited Paper, Proc. 21st annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2001, Lecture Notes in Computer Science 2245, pp. 1-15.

Time-Space Tradeoffs in the Counting Hierarchy,
(with Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay), in Proc. 16th Annual IEEE Conference on Computational Complexity (CCC), 2001, pp. 295-302.

Basic Complexity,
(with Catherine McCartin), in Aspects of Complexity, de Gruyter Series in Logic and Its Applications, Volume 4, edited by Rod Downey and Denis Hirschfeldt, 2001, pp. 1-28.

Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front,
in Current Trends in Theoretical Computer Science: Entering the 21st Century, edited by G. Paun, G. Rozenberg, and A. Salomaa, World Scientific Press, 2001, pp. 25-41. Parts of this work appeared earlier in two columns in The Computational Complexity Column, of the Bulletin of the EATCS.

Reducing the complexity of reductions,
(with Manindra Agrawal, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich), Computational Complexity 10 (2001) 117-138. Springer provides free read-only access to this publication. A preliminary version appeared in Proc. 29th STOC 1997, pp. 730-738.
ACM DL Author-ize serviceReducing the complexity of reductions
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 1997

A Lower Bound for Primality,
(with Michael Saks and Igor Shparlinski) Journal of Computer and System Sciences 62 (2001) 356-366. Special issue on CCC 1999. Prelininary version appeared in Proc. 14th Annual IEEE Conference on Computational Complexity (CCC), 1999, pp. 10-14.

Characterizing Small Depth and Small Space Classes by Operators of Higher Types,
(with Manindra Agrawal, Samir Datta), Heribert Vollmer, and Klaus W. Wagner),
Chicago Journal of Theoretical Computer Science, 2000, article 2.

Complexity of Finite-Horizon Markov Decision Process Problems,
(with Martin Mundhenk, Judy Goldsmith, and Christopher Lusena). Journal of the ACM 47 (2000) 681 - 720. An earlier version, entitled The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes , appeared in MFCS 1997, Lecture Notes in Computer Science 1295, pp. 129-138. !-- ACM DL Article: Complexity of finite-horizon Markov decision process problems -->

Making nondeterminism unambiguous,
(with Klaus Reinhardt), SIAM J. Comp. Vol. 29, 2000, 1118-1131. An earlier version appeared in FOCS 1997, pp. 244-253.

On TC^0, AC^0, and Arithmetic Circuits,
(with Manindra Agrawal and Samir Datta), Journal of Computer and System Sciences 60 (2000) 395-421. Special issue on CCC 1997. An earlier version appeared in the twelfth Annual IEEE Conference on Computational Complexity (CCC), 1997.

Bounded Depth Arithmetic Circuits: Counting and Closure,
(with Andris Ambainis, David A. Mix Barrington, Samir Datta, and Huong LêThanh), Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP), 1999, Lecture Notes in Computer Science 1644, pp. 149-158.

Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds,
(with Klaus Reinhardt and Shiyu Zhou), Journal of Computer and System Sciences 59 (1999) 164-181. Special issue on CCC 1998. (This material appeared in preliminary form in the papers Isolation, Matching, and Counting ( Proc. 13th Annual IEEE Conference on Computational Complexity (CCC), 1998, pp. 92-100), and Uniform Inclusions in Nondeterministic Logspace (Workshop on Randomized Algorithms, 1998.))

The complexity of matrix rank and feasible systems of linear equations,
(with Robert Beals and Mitsunori Ogihara). Computational Complexity, Vol. 8, 1999, 99-126. Springer provides free read-only access to this publication. A preliminary version appeared in Proc. 28th STOC 1996, pp. 161-167.
ACM DL Author-ize serviceThe complexity of matrix rank and feasible systems of linear equations (extended abstract)
Eric Allender, Robert Beals, Mitsunori Ogihara
STOC '96 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996

The Permanent Requires Large Uniform Threshold Circuits,
Chicago Journal of Theoretical Computer Science, 1999, article 7. An earlier version, entitled A note on Uniform Circuit Lower Bounds for the Counting Hierarchy, appeared in the 2nd Annual International Computing and Combinatorics Conference (COCOON 1996), Lecture Notes in Computer Science 1090, pp. 127-135.

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem,
(with Manindra Agrawal and Steven Rudich), Journal of Computer and System Sciences Vol. 57, 1998, 127-143. Special issue on CCC 1996. An earlier version, entitled An Isomorphism Theorem for Circuit Complexity, appeared in the Eleventh Annual IEEE Conference on Computational Complexity (CCC) (1996).

Non-commutative arithmetic circuits: depth reduction and size lower bounds,
(with Jia Jiao, Meena Mahajan, and V. Vinay), Theoretical Computer Science Vol. 209, 1998, 47-86. [NOTE:The proof of Theorem 7.12 is incorrect. See the discussion of this here.] This is a revision and extension of the paper Depth reduction for noncommutative arithmetic circuits (with Jia Jiao), in Proc. 25th STOC 1993, pp. 515-522.
ACM DL Author-ize serviceDepth reduction for noncommutative arithmetic circuits
Eric Allender, Jia Jiao
STOC '93 Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, 1993

RUSPACE(log n) is contained in DSPACE(log^2 n/loglog n),
(with Klaus-Jörn Lange). Theory of Computing Systems, Vol. 31, 1998, pp. 539-550. Special issue devoted to the 7th Annual International Symposium on Algorithms and Computation ( ISAAC '96). Springer provides free read-only access to this publication. The conference version was entitled StUSPACE(log n) is contained in DSPACE(log^2 n/loglog n).

A first-order isomorphism theorem,
(with José Balcázar and Neil Immerman), SIAM J. Comp. Vol. 26, 1997, pp. 557-567. An earlier version appeared in Proc. 10th International Symposium on Theoretical Aspects of Computer Science (STACS), 1993, Lecture Notes in Computer Science 665, pp. 163-174.

Circuit Complexity Before the Dawn of the New Millennium,
Invited Paper, Proc. 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS '96), Lecture Notes in Computer Science 1180, pp. 1-18, 1996.

Relationships among PL, #L, and the determinant,
(with Mitsunori Ogihara), RAIRO - Theoretical Informatics and Applications Vol. 30, 1996, pp. 1-21. (See also a comment on this paper, entitled "A clarification concerning the #L hierarchy", which was later incorporated into an appendix of Arithmetic Circuits and Counting Complexity Classes.) An earlier version appeared in Proc. 9th IEEE Structure in Complexity Theory Conference, 1994, pp. 267-278.

Measure on P: robustness of the notion,
(with Martin Strauss), MFCS 1995, Lecture Notes in Computer Science 969, pp. 129-138.

Measure on small complexity classes, with applications for BPP,
(with Martin Strauss), FOCS 1994, pp. 807-818.

Algebraic methods for proving lower bounds in circuit complexity,
Proc. Workshop on Algebraic Methods in Complexity Theory, December, 1994, Institute of Mathematical Sciences, Madras, India.

A uniform circuit lower bound for the permanent,
(with Vivek Gore), SIAM Journal on Computing Vol. 23, 1994, pp. 1026-1049.

Depth reduction for circuits of unbounded fan-in,
(with Ulrich Hertrampf), Information and Computation Vol. 112 1994, pp. 217-238. (This material appeared in preliminary form in the papers A Note on the Power of Threshold Circuits (FOCS 1989, pp. 580-584), and On the Power of Uniform Families of Constant-Depth Threshold Circuits (MFCS 1990, Lecture Notes in Computer Science 452, pp. 158-164.))

On strong separations from AC^0,
(with Vivek Gore), in Advances in Computational Complexity Theory, Jin-Yi Cai, ed., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 13, AMS Press, 1993, pp. 21-37. An earlier version appeared in Proc. 8th International Conference on Fundamentals of Computation Theory (FCT '91), Lecture Notes in Computer Science 529, pp. 1-15.

Counting hierarchies: polynomial time and constant depth circuits
(with Klaus W. Wagner), in Current Trends in Theoretical Computer Science, edited by G. Rozenberg, and A. Salomaa, World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 469-483. This work appeared earlier in The Computational Complexity Column, of the Bulletin of the EATCS.

The complexity of computing maximal word functions,
(with Danilo Bruschi and Giovanni Pighizzini), Computational Complexity 3, 1993, pp. 368-391. Springer provides free read-only access to this publication.

Almost-everywhere complexity hierarchies for nondeterministic time,
(with Richard Beigel, Ulrich Hertrampf, and Steven Homer), Theoretical Computer Science Vol. 115, 1993, pp. 225-242. An earlier version appeared in Proc. 7th Symposium on Theoretical Aspects of Computer Science (STACS 1990), Lecture Notes in Computer Science 415, pp. 1-11.

Applications of time-bounded Kolmogorov complexity in complexity theory,
in Kolmogorov Complexity and Computational Complexity, Osamu Watanabe, editor, EATCS Monograph Series, Springer-Verlag, 1992, pp. 4-22. Earlier versions of this work appeared in Proc. AAAI Spring Symposium on the Theory and Application of Minimal-Length Encoding, and in a paper entitled The Generalized Kolmogorov Complexity of Sets, in Proc. 4th IEEE Structure in Complexity Theory Conference, 1989.

Relating equivalence and reducibility to sparse sets,
(with Lane Hemachandra, Mitsunori Ogihara, and Osamu Watanabe), SIAM Journal on Computing Vol. 21, 1992, pp. 521-539. An earlier version appeared in Proc. 6th IEEE Structure in Complexity Theory Conference, 1991.

Lower bounds for the low hierarchy,
(with Lane Hemachandra), Journal of the ACM 39 (1992) 234 - 251. An earlier version appeared in Proc. 16th International Colloquium on Automata, Languages, and Programming (ICALP 1989), Lecture Notes in Computer Science 372, pp. 31-45.

Rudimentary reductions revisited,
(with Vivek Gore), Information Processing Letters Vol. 40, 1991, pp. 89-95.

Limitations of the Upward Separation Technique,
Mathematical Systems Theory 24 (1991) 53-67. An earlier version appeared in Proc. 16th International Colloquium on Automata, Languages, and Programming (ICALP 1989), Lecture Notes in Computer Science 372, pp. 18-30.

Oracles vs Proof techniques that do not relativize,
in Proc. SIGAL International Symposium on Algorithms, 1990, Lecture Notes in Computer Science 450, pp. 39-52.

Width-bounded reducibility and binary search over complexity classes,
(with Chris Wilson) in Proc. 5th Annual IEEE Structure in Complexity Theory Conference, 1990, pp. 122-129.

Downward translations of equality,
(with Chris Wilson), Theoretical Computer Science Vol. 75, 1990, pp. 335-346.

Kolmogorov complexity and degrees of tally sets,
(with Osamu Watanabe), Information and Computation Vol. 86 1990, pp. 160-178. An earlier version appeared in Proc. 3rd IEEE Structure in Complexity Theory Conference, 1988.

P-uniform circuit complexity,
Journal of the ACM 36 (1989) 912 - 928.
ACM DL Author-ize serviceP-uniform circuit complexity
Eric W. Allender
Journal of the ACM (JACM), 1989
An earlier version, entitled Characterizations of PUNC and Precomputation, appeared in Proc. 13th International Colloquium on Automata, Languages, and Programming (ICALP 1986), Lecture Notes in Computer Science 226, pp. 1-10.

Some consequences of the existence of pseudorandom generators,
Journal of Computer and System Sciences Vol. 39, 1989, 101-124. Special issue on IEEE Structure in Complexity Theory Conference 1987 (whose proceedings contain an abstract of this paper). An earlier version appeared in Proc. 19th STOC, 1987, pp. 151-159.
ACM DL Author-ize serviceSome consequences of the existence of pseudorandom generators
E. Allender
STOC '87 Proceedings of the nineteenth annual ACM symposium on Theory of computing, 1987

On generating solved instances of computational problems,
(with Martin Abadi, Andrei Broder, Joan Feigenbaum, and Lane Hemachandra), in Advances in Cryptology, Proc. CRYPTO '88, Lecture Notes in Computer Science 403, 1990, pp. 297-310.

P-printable sets,
(with Roy Rubinstein), SIAM Journal on Computing Vol. 17, 1988, pp. 1193-1202. An earlier version, entitled The Complexity of Sparse Sets in P, appeared in Proc. 1st Structure in Complexity Theory Conference, 1986, Lecture Notes in Computer Science 223, pp. 1-11.

Isomorphisms and 1-L reductions,
Journal of Computer and System Sciences Vol. 36, 1988, 336-350. Special issue on Structure 1986. An earlier version appeared in Proc. 1st Structure in Complexity Theory Conference, 1986, Lecture Notes in Computer Science 223, pp. 12-22.

Solution to an open problem of J. Hromcovic,
Bulletin of the EATCS 26, June, 1985, 243-244.

Improved lower bounds for the cycle detection problem,
(with Maria Klawe), Theoretical Computer Science Vol. 36, 1985, pp. 231-237.

On the number of cycles possible in digraphs with large girth,
Discrete Applied Mathematics Vol. 10, 1985, pp. 211-225.

Invertible Functions (Chapters 1-3) (Chapters 4-9), Doctoral Dissertation, Georgia Institute of Technology, 1985.
As a public service, I also provide a few pointers to hard-to-find articles that I have cited.