Changes in TCS

At the first BAM, I got an idea of how little complexity theory has changed in three decades: after I described Morgenstern's lower bound for arithmetic circuits with bounded constants, Christos noted that he gave a talk about the same paper in 1978, when he was a postdoc at Berkeley. We still have no clue how to prove a superlinear lower bound in the unrestricted model.

At the same meeting, I got to observe a change in the people that define our community, a change that fed right into my anxiety that "Theory of Computer Science" is becoming "Theory." After I defined and drew a butterfly graph, I asked how many people have seen this before; some 3 or 4 people raised their hands (which drops to a very small number once you subtract Christos and Dick Karp). But when I asked who knew that "Fourier characters are orthogonal," all but one had their hands up!

I, for one, grew up thinking supercomputers were cool, and knew all about routing messages, before I learned about those "linear systems" that people apparently wanted to solve on big machines. And, yes, I am suspicious of people who had a "theory is cool!" moment before 100 "CS is cool!" moments.