ABSTRACT. This month marks an important anniversary.  It was precisely 3³ years ago (July, 1987) that Neil Immerman announced a proof that NL = coNL. This shook the complexity-theoretic universe, triggering the collapse of multiple hierarchies, and spawning a series of aftershocks that still reverberate. This lecture will survey some of these developments, and will also trace the impact of some work of Immerman and Landau, which brought to the fore the central role that is played by iterated multiplication (in different algebras), in elucidating the structure of subclasses of P.

ABSTRACT. In 1982, Neil Immerman proposed an extension of fixed-point logic by means of counting quantifiers (which we denote FPC) as a logic that
might express all polynomial-time properties of unordered structures.  It was eventually proved (by Cai, Fürer and Immerman) that there are
polynomial-time graph properties that are not expressible in FPC. Nonetheless, FPC is a powerful and natural fragment of the complexity class P.  In this talk, I will demonstrate this point by reviewing three recent results on the expressive power of FPC.