Expository Articles and Surveys

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 appeared in the Complexity Theory Column, edited by Lane Hemaspaandra, SIGACT NEWS 28, 4 (December, 1997) pp. 2-15.

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.

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.

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.

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.

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.

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.