Reading group on The Nature of Computation

We are reading the book The Nature of Computation by Cristopher Moore and Stephan Mertens.

All chapters are available for download as PDFs from here if you access the page via the university library's web proxy.

Everyone reads the relevant part of the book before each meeting, but each meeting will also have a facilitator who will briefly summarize the contents of the chapter and then lead some discussion or present some exercises from the book that we do together etc. The facilitator gets to decide the structure of the meeting as they find fitting. We'll change who is the facilitator in a round-robin schedule where everyone gets an even share of this responsibility.

(Note: Being a facilitator does not mean that you have to deliver any type of lecture and does not mean that you have to understand the topics better than others. It's simply the person who structures the meeting if necessary.)

When What Who
2021-02-16 Chapter 1 + 2 - Prologue + The Basics Pontus
2021-03-02 Chapter 3 - Insights and Algorithms Chencheng
2021-03-16 Chapter 4 - Needles in a Haystack: the Class NP Zafer
2021-03-30 Chapter 5 - Who is the Hardest One of All? NP-Completeness Gaoyang
2021-04-13 Chapter 6 - The Deep Question: P vs. NP Samuel
2021-04-27 Chapter 7 - The Grand Unified Theory of Computation Amanda
2021-05-11 Chapter 8 - Memory, Paths, and Games Riccardo
2021-05-25 Chapter 9 (Sections 9.1 - 9.5) - Optimization and Approximation Nick
2021-06-08 Chapter 9 (Sections 9.6 - 9.10) - Optimization and Approximation Morteza
2021-06-22 Reflections before summer (no reading) Everyone
☀️ Summer, and then some ☀️
2022-01-25 Chapter 10 (Sections 10.1 - 10.5) - Randomized Algorithms Chencheng
2022-02-08 Chapter 10 (Sections 10.6 - 10.9) - Randomized Algorithms Zafer
2022-02-22 Chapter 11 (Sections 11.1 - 11.2) - Interaction and Pseudorandomness Gaoyang
2022-03-08 Chapter 11 (Sections 11.3 - 11.4) - Interaction and Pseudorandomness Samuel
2022-03-22 Chapter 12 (12.1 - 12.6) - Random Walks and Rapid Mixing Nick
2022-04-05 Chapter 12 (12.7 - 12.10) - Random Walks and Rapid Mixing Chencheng
2022-04-19 Chapter 13 (13.1 - 13.4) - Counting, Sampling, and Statistical Physics Zafer
2022-05-03 Chapter 13 (13.5 - 13.7) - Counting, Sampling, and Statistical Physics Gaoyang
2022-05-24 Chapter 14 (14.1 - 14.4) - When Formulas Freeze: Phase Transitions in Computation Samuel
2022-06-07 Chapter 14 (14.5 - 14.8) - When Formulas Freeze: Phase Transitions in Computation Nick
☀️ Summer ☀️
2023-01-20
13:00-15:00
in Å105190		 Chapter 15 (15.1 - 15.3) - Quantum Computation Pontus
2023-02-03
13:00-15:00
in Å105190		 Chapter 15 (15.4 - 15.5) - Quantum Computation TBD
2023-02-17
13:00-15:00
in Å105190		 Chapter 15 (15.6 - 15.8) - Quantum Computation TBD