Albert Meyer

Abstract here

This talk is on the close relationship between computational problems for Petri nets (a model for distributed computation, invented by C.A. Petri in Germany, but brought to prominence by Project MAC at MIT) and algebraic structures like commutative semigroups and polynomial ideals. For the latter, work with Albert showed that the complexity of these structures is way beyond what people intuitively expected.

In the early years of computational complexity, Albert Meyer helped guide the field into making sure we got it right. He and his colleagues had several early results on computation models, abstract complexity, a tight nondeterministic time hierarchy, and the first provably hard problem. His seminal work on the polynomial-time hierarchy with Larry Stockmeyer gave the field a grand structure to understand the difficulty of computational problems. This talk will explore Albert Meyer's research in complexity and its legacy through the present and beyond.

Like the first phase of Albert Meyer's outstanding research career, most of American theoretical computer science is directed toward algorithms and computational complexity. The leading international conferences, STOC and FOCS, created or renamed 1969-1975, are largely oriented in this direction. Following influential papers on the logic and semantics of while programs and models of lambda calculus, Albert Meyer founded and chaired the initial 1986 meeting of the Logic in Computer Science conference, which remains a lively "Theory B" counterpart to the "Theory A" conferences and intellectual traditions. Why would a leading complexity theorist of the day move his focus to logic and semantics? What value and perspective does this area bring to the field of computer science as a whole? This talk will ponder these question, reflecting on the work of Albert Meyer and some of the speaker's own interests related to the theory of programming languages and computer security.

I'll discuss some of Albert's work on logics of programs, and what it was like being his student.

At the dawn of AI in the 1950s and 60s mathematical logic was viewed as the central intellectual paradigm for understanding intelligence. AI was dominated by "logicists" lead by John McCarthy. While logic is far less influential in the AI today, the centrality of mathematics in science and technology, and particularly in software engineering, implies that logic must ultimately be important for machine thought. Although Albert has not been comfortable with the Logic-AI connection, this talk will spin Albert's work as a contribution to AI. Current trends in the foundations of mathematics (Homotopy Type Theory) will also be discussed from an AI perspective.