Overview

About the Course: This course explores computational complexity, from search algorithms and solution landscapes toreductions and universality. We explore problems ranging from easy (polynomial time) to hard (NP-complete) to impossible (undecidable). These ideas formone of the most beautiful fields of modernmathematics, and they are increasingly relevant to sciences ranging from physics to biology. The aim ofthis course is to help participants gain an understanding of the deep ideas of theoretical computerscience in a clear and enjoyable fashion, making those ideas accessible both to non-computer scientists andto computer scientists who want to revisit these ideas in a broader and deeper way. Units include: Easy and Hard Algorithms and Landscapes P versus NP Worst-case, Natural, and Random 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. About the Instructor(s): 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 atcole 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 ofThe Nature of Computationfrom Oxford University Press. Course Team: John Malloy(he/him) - Teaching Assistant John is a PhD student at ArizonaState 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 pharmaceuticalchemistry and scientific citation networks, he hopes to quantify evolutionary patterns which apply to non-DNA-basedlife. 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 [email protected]