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
Learning Resources
Course notes, online readings, course discussion board
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.
Pre-required Knowledge
Some elementary programming experience. No mathematics background beyond high school mathematics is expected.
Assessment Structure
Weekly homework. No exams.
Course Link
http://computationallens.com