The Computational Lens Course ID 15155 Description What is knowable, in principle and in practice? - What does it mean to be intelligent? - Can creativity be automated? - What is the role of randomness in the universe? - How can we achieve provable guarantees of security, privacy, fairness, etc. in various settings? - What does the social network of the world look like? - Do we live in a simulation? Despite their differences, all of these questions are fundamentally about the notion of computation. And all these questions can be put under the following single umbrella: What is computation and how does it shape our understanding of life, science, technology, and society? This course is for anyone interested in these questions and more broadly, anyone interested in the algorithmic lens to tackle hard, foundational problems. Our goal will be to find reliable explanations through modeling and rigorous reasoning. We will discuss great and powerful ideas from the field of theory of computation and see how these ideas shed new light on human reasoning, laws of nature, life, technology, and society. Key Topics Introduction to mathematical reasoning Formalization of computation Uncountability Uncomputability Unprovability Computational complexity Graph/network theory P vs NP Overview of randomness in computer science Randomized algorithms Cryptography Quantum computation Statistical physics Learning theory Evolution as a learning algorithm Fair division Algorithmic game theory Interactive Proofs Required Background Knowledge Some elementary programming experience. No mathematics background beyond high school mathematics is expected. Course Relevance Theory of computation is one of the richest and deepest intellectual fields with connections to computer science & engineering, mathematics, physics, biology, statistics, philosophy, social sciences, economics, etc. The reason for this is that computation (i.e. information processing) is very fundamental, and in many systems ¿ whether natural or human-made, primitive or emergent ¿ the most important or relevant aspect of the system is how information evolves. Theory of computation brings powerful ideas and techniques like modeling, abstractions, algorithms, reductions, classifications, etc. that help us push the boundaries of what we know, what we understand, and what we can explain. Future intellectuals and leaders, whether they have a technical background or not, should recognize the true nature of computation as one of the pillars of human knowledge, understanding and discovery. Course Goals Define the notions of computation, algorithm, and computational complexity. Express and compare the computability and computational complexity of problems. State and give examples of the connections of the theory of computation with mathematics, physics, biology, statistics, philosophy, social sciences and economics. State and give examples of technological real-world applications of the theory of computation. Recognize the use of ideas and techniques from the theory of computation, like modeling, abstraction, algorithmic thinking, reductions, classifications. State and explain the important and well-known open problems in the theory of computation and their connections to other fields. Learning Resources Course notes, online readings, course discussion board Assessment Structure Weekly homework. No exams. Course Link http://computationallens.com
