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

**Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization**,-
to appear in a special issue of
New Zealand Journal of
Mathematics 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. **Depth-First Search in Directed Planar Graphs, Revisited**,- (with
Archit
Chauhan and
Samir Datta),
Proc.
46th International Symposium
on Mathematical Foundations of Computer Science (MFCS '21),
Leibniz International Proceedings in Informatics (LIPIcs) 202,
pp. 7:1 -- 7:22.
See also
ECCC Report
TR20-074, 2020.
**One-way Functions and a Conditional Variant of MKTP**,- (with
Mahdi Cheraghchi,
Dimitrios Myrisiotis,
Harsha Tirumala,
and
Ilya Volkovich
),
ECCC Report
TR21-009, 2021.
**Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity**,- (with
John Gouwar,
Shuichi Hirahara,
and Caleb Robelle ),
to appear in Proc. 32nd International
Symposium on Algorithms and Computation (ISAAC 2021).
See also
ECCC Report
TR21-010, 2021.
**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.
**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. **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)*, 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. **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 Science 8635, pp. 13-24, 2014.
**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, 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, 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, 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 (Marvin Zelkowitz, editor), Academic Press, 2009, pp. 118-147. **Computational Complexity Theory**,- in
*Encyclopedia of Computer Science and Engineering,*(Benjamin Wah, editor in chief), Volume 1, Wiley Interscience, 2009, pp. 500-506. **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, 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, 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, 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. **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, 2005, pp. 298-307.
**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.
Making computation count: arithmetic circuits in the ninetiesEric Allender

ACM SIGACT News, 1997 **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. An earlier version appeared as**Uniform Circuits for Division: Consequences and Problems**,*Proc. 16th Annual IEEE Conference on Computational Complexity*, 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*, 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.Reducing the complexity of reductionsManindra 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*, 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,*LNCS*1295, pp. 129-138. **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, 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*, 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.The 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 (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. 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.Depth reduction for noncommutative arithmetic circuitsEric 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.) 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,*LNCS*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,*LNCS*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.P-uniform circuit complexityAn earlier version, entitledEric W. Allender

Journal of the ACM (JACM), 1989**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.Some consequences of the existence of pseudorandom generatorsE. 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.