A Quest for Structure in Complexity

Abstract

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.