Early Theory

Susan Graham is a Distinguished Professor of Electrical Engineering and Computer Science Emerita at the University of California, Berkeley. I have known Graham for decades—and am happy to report she is still active.

She was a member of the President’s Council of Advisors on Science and Technology (PCAST) during the Obama Administration. She served alongside Bill Press of Austin, who is still on PCAST—alongside Terry Tao among names we know.

Graham has maintained involvements in the performing arts. She is an Officer on the Board of Trustees of Cal Performances. She also served on the Board of Overseers of the Curtis Institute of Music in Philadelphia until they reorganized in 2016. She has also had a long association with Harvard, She was referring to committee memberships when she was quoted for the subtitle above, but her words “everything is interesting” apply more widely in our field.

Her Work

Graham has done seminal research in compiler code generation and optimization. She was elected a member of the National Academy of Engineering in 1993 for contributions to the theory and practice of compiler construction and for leadership in the computer science community. And was awarded the 2009 IEEE John von Neumann Medal for “contributions to programming language design and implementation and for exemplary service to the discipline of computer science.”

The nexus with programming languages was arguably the initial focus of computer science theory in the years before 1965, when Juris Hartmanis and Richard Stearns founded computational complexity on Turing machines. See the history penned by John Savage, Alan Selman, and Carl Smith for a neat summary.

They point out:

After the early recognition of the relevance of the theory of formal languages to the practice of compiler construction, theoretical computer science became a cornerstone of virtually every computer science undergraduate degree program.

Susan’s first paper appeared at the conference now named FOCS in 1970. It was titled, “Extended Precedence Languages, Bounded Right Context Languages, and Deterministic Languages.” Rather than invent a new complexity class, as even ChatGPT picked up on our common vice recently, she more economically collapsed some classes together.

The combination of “theoretical and practical interest” as mentioned in her paper carried through to much other work in programming languages and their implementations, software tools and development environments, and needs of high-performance computing. Her work with students on the Berkeley Unix project led to their paper on the program profiling tool gprof. This is considered one of the classic papers from the Programming Language Design and Implementation (PLDI) conferences.

Open Problems

Graham is terrific. I only hope that she is able to help us better understand theory of all types.