Date: November 2, 2026
Title: On the Computational Basis of Natural Language
Speaker: Christos Papadimitriou, Donovan Family Professor of Computer Science, Columbia University

Abstract: Language is clearly computational: it is combinatorial, and understanding and producing utterances involves substantial processing. Yet its computational basis (the specific abstract operations needed to learn, process, and generate language) remains poorly understood. Starting in the late 1950s, Chomsky argued that because children acquire language from remarkably limited input, they must be born with a specialized faculty, later called universal grammar. He said little about how this faculty works until, decades later, he proposed Merge (an operation that combines two items into a new one, and so builds trees) as the core of human linguistic ability. Many linguists have disagreed, arguing instead that we learn language with general-purpose learning mechanisms, statistical learning among them. With Dan Mitropolsky, we have built a language acquisition system from biologically realistic neurons, Hebbian synapses, and brain areas. Given roughly the amount of grounded input a child receives, it acquires language at a level comparable to the second year of life. I will review this story and present mathematical results showing that the system behaves broadly as experiments indicate human acquisition does. Our results suggest that the computational basis of natural language may consist of (a) a specific form of statistical learning, (b) a suite of neural operations reminiscent of Merge, and (c) a neural mechanism that learns, once and for life, a linear order among brain areas.
Bio: Christos Harilaos Papadimitriou is the Donovan Family Professor of Computer Science at Columbia University. Before joining Columbia in 2017, he was a professor at UC Berkeley for the previous 22 years, and before that he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and language and the brain. He holds a Ph.D. from Princeton (1976), and ten honorary doctorates, including from ETH, University of Athens, EPFL, and Univ. de Paris Dauphine. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and he has received the Knuth prize, the Gödel prize, the von Neumann medal, as well as the 2018 Harvey Prize by Technion. In 2015 the president of the Hellenic republic named him commander of the order of the Phoenix. He has also written three novels: “Turing”, “Logicomix”, and his latest “Independence.”