аÄÃÅÁùºÏ²ÊÄÚÄ»ÐÅÏ¢

2024 Nagle Lecture

Easy, Hard, and Impossible: The Limits of Computation 

About the Event

Every day we ask computers to solve problems for us – to find the fastest route across town, the shape a protein folds into, or a proof for an unsolved mathematical question. For all these problems, the space of possible solutions is vast. Why is that for some problems, we can quickly zoom in on the solution, while for others it's like looking for a needle in a haystack? What it is about the structure of a problem that makes it easy, or hard, or even impossible to solve? Moore will draw analogies between computation and evolution and take us from the simple puzzles to the heights of universal computation, Turing's halting problem, and the nature of mathematical truth and creativity. 

 

---

ABOUT THE SPEAKER

Cris Moore, Santa Fe Institute 

Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute. He has also held visiting positions at the Niels Bohr Institute, École Normale Superieure, École Polytechnique, Université Paris 7, Northeastern University, the University of Michigan, and Microsoft Research. 

Moore has written over 160 papers at the boundary between mathematics, physics, and computer science, ranging from quantum computing, social networks, and phase transitions in NP-complete problems and Bayesian inference, to risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.  
‌Moore collaborated with the Santa Fe Symphony on an award-winning PBS documentary, The Majesty of Music and Mathematics, which has been broadcast widely. His non-technical writing on mathematics has appeared in Nautilus and The American Scholar. Most recently, he and his colleagues in the Interdisciplinary Working Group on Algorithmic Justice have analyzed risk assessment algorithms for accuracy and fairness and argued against the use of proprietary algorithms in housing and pretrial supervision. 

---

PARKING

Guest parking is available at аÄÃÅÁùºÏ²ÊÄÚÄ»ÐÅÏ¢Research Park South Building.

For more information about guest parking options, please visit Parking Services.

аÄÃÅÁùºÏ²ÊÄÚÄ»ÐÅÏ¢Campus Map (PDF)

For reasonable accommodations or other questions, please contact CAS RSVP.