A Quest for Structure in Complexity
V. Arvind, Meena Mahajan · Bulletin of the European Association for Theoretical Computer Science · 2017
Eric Allender turned sixty some months ago, and in this October computational complexity column we will describe some highlights of his research work spanning over three decades. His research career began in 1985. The “Structure in Complexity Conference” was born in 1986. Although FOCS and STOC remain the primary conferences for theoretical computer science, “Structures” was a more niche conference devoted to complexity theory. In the first Structures Conference, in 1986, Eric had two papers. The computational complexity column in the EATCS bulletin was started in 1987 (with Juris Hartmanis as editor). All roughly around the same time. The field has rapidly grown over the last three decades, and Eric has played a prominent role shaping modern computational complexity theory in a range of topics. His work has also given rise to several new directions of research. In this article, we pick some of our favorite themes from Eric’s research: Kolmogorov complexity and circuit minimization, the isomorphism problem and the structure of complete problems in complexity classes, the landscape of space-bounded complexity classes, and circuit complexity lower bounds. Eric himself has a number of excellent comprehensive survey articles on these topics [24, 22, 21, 23]. This column article is meant to serve as an appetizer inviting the reader to these surveys.