Complexity Explorer Santa Few Institute

This course explores computational complexity, from search algorithms and solution landscapes to reductions and universality. We explore problems ranging from easy (polynomial time) to hard (NP-complete) to impossible (undecidable). These ideas form one of the most beautiful fields of modern mathematics, and they are increasingly relevant to sciences ranging from physics to biology. The aim of this course is to help participants gain an understanding of the deep ideas of theoretical computer science in a clear and enjoyable fashion, making those ideas accessible both to non-computer scientists and to computer scientists who want to revisit these ideas in a broader and deeper way.

Units include:

1. Easy and Hard
2. Algorithms and Landscapes
3. P versus NP
4. Worst-case, Natural, and Random
5. Computation Everywhere

Units will be released approximately one per week, with a unit exam at the end of each and due by the end of the subsequent week (eg. unit 1 released at start of week 1; unit 1 exam due at the end of week 2). Each unit will require an average of about 5 hours to complete (including all content and assessments). All coursework is conducted in English.

The course consists of lectures, interactive exercises, quizzes for self-assessment, and unit exams. The interactive exercises allow participants to see various problems from the lectures in practice and to see the effects of various perturbations. The quizzes are intended to help participants assess their understanding of the material and to prepare for the unit exams. Only the unit exam scores count toward completion of the course, which requires that a participant achieve ≥ 60% score on all unit exams. The unit exams consist of quiz questions and are peer-graded according to a grading rubric provided by the instructor. Completion of grading assignments is also required to recieve a certificate of completion for the course.

Cristopher Moore - Course Instructor

Cris Moore is resident faculty at the Santa Fe Institute. He 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. He has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, the University of Michigan, and Northeastern University. He has written 150 papers at the boundary between physics and computer science, ranging from quantum computing, to phase transitions in NP-complete problems, to the theory of social networks and efficient algorithms for analyzing their structure. 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. 

John Malloy (he/him) - Teaching Assistant

John is a PhD student at Arizona State University. He received his B.S. in Bioinformatics and Computational Biology from University of Maryland, Baltimore County, as well as a M.F.A in Teaching from Notre Dame of Maryland University. He studies astrobiology, the search for life on other planets, through exploring the evolution of network-based systems with non-biological evolutionary pressures. Through systems such as pharmaceutical chemistry and scientific citation networks, he hopes to quantify evolutionary patterns which apply to non-DNA-based life. Outside of astrobiology, he can be found working to advance science-based policy measures in Arizona and training for ultramarathons throughout the American Southwest. 

For course specific inquiries, please contact computation@complexityexplorer.org