Christos Papadimitriou

Thursday, April 11, 2019 at 11:00 am

Christos Papadimitriou - Computation in the Brain

Donovan Family Professor of Computer Science
Columbia University

Professor Emeritus
Berkeley University

Abstract: How does the brain beget the mind? How do molecules, cells and synapses effect reasoning, intelligence, language, science? Despite dazzling progress in experimental neuroscience we do not seem to be making progress in the overarching question – the gap is huge and a completely new approach seems to be required. As Richard Axel recently put it: “We don’t have a logic for the transformation of neural activity into thought.”

What kind of formal system would qualify as this “logic”? I will sketch a possible answer.

(Joint work with Santosh Vempala, Wolfgang Maass, Larry Abbott, Dan Mitropolsky, and Mike Collins.)

Bio: Christos H. 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 the brain. He holds a PhD from Princeton (1976) and an honorary doctorate from Univ. de Paris Dauphine (2017), and seven other honorary doctorates. 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 Godel prize, and the von Neumann medal. He has also written three novels: “Turing”, “Logicomix” and his latest “Independence”.

Host: Avrim Blum

Ran Raz

Tuesday, May 7, 2019 at 11:00 am

Ran Raz - Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning

Professor of Computer Science
Princeton University

Bio: Ran Raz is a professor of computer science at Princeton University. Raz received his B.Sc. in mathematics and physics (1987) and Ph.D. in mathematics (1992) from the Hebrew University of Jerusalem. After a post-doctoral fellowship at Princeton he joined the faculty at the Weizmann Institute of Science. He was a visiting professor at the Institute for Advanced Study and at Microsoft Research. Raz’s main research area is complexity theory, with a focus on proving lower bounds for computational models. More specifically, he is interested in Boolean and arithmetic circuit complexity, communication complexity, probabilistically checkable proofs, quantum computation and communication, and randomness and derandomization.

Host: Yury Makarychev

All talks will be held at TTIC in room #526/530 located at 6045 South Kenwood Avenue (intersection of 61st street and Kenwood Avenue)

Parking: Street parking, or in the free lot on the corner of 60th St. and Stony Island Avenue.

For questions and comments contact Nathan Srebro.