Learning shelf · Links checked 1 Nov 2026
Build enough theoretical computer science to read AI claims carefully. This page groups official starting points by purpose: foundations, core theory, video lectures and formal proofs.
Foundations · Start here
These resources are not about AI. They reduce the chance that a research paper or a dramatic headline sounds difficult only because its basic mathematical language is unfamiliar.
MIT OpenCourseWare
Build a foundation in proofs, sets, graphs, counting and discrete probability. Use it before more specialised theory if the notation in papers feels unfamiliar.
Keep in mind: This is general mathematical preparation, not a course about AI or complexity research.
Open official resourceJeff Erickson
A rigorous but readable introduction to algorithm design, analysis and correctness, with exercises and proofs.
Keep in mind: It teaches algorithms, not the full landscape of complexity theory or AI research.
Open official resourceCore theory
Algorithms, computability and complexity are the backbone of the claims discussed elsewhere on this site. Learn the definitions before debating whether a headline has overturned them.
Boaz Barak
Connects computation, automata, computability and complexity through a modern textbook format. It is a useful bridge from programming to theory.
Keep in mind: Check the edition, errata and recommended background on the official page.
Open official resourceMIT OpenCourseWare
A proof-based course covering automata, computability and complexity, with lecture notes and assessments available through MIT OpenCourseWare.
Keep in mind: It expects mathematical maturity and is not an AI-specific survey.
Open official resourceSanjeev Arora and Boaz Barak
A broad treatment of modern complexity theory, including core complexity classes, circuit complexity, proof complexity and probabilistically checkable proofs.
Keep in mind: Use the official page to check the edition and corrections before citing a passage.
Open official resourceVideo lectures
Complete lecture sequences show definitions, examples and proof steps in order. A short social video can point to a topic, but it cannot replace that chain of reasoning.
Tim Roughgarden
Video lectures and a companion book series explain algorithm design and analysis in a paced, example-driven sequence.
Keep in mind: The focus is algorithms, not AI research or complexity-theory proof techniques.
Open official resourceCarnegie Mellon University
Lectures and notes on mathematical tools used in theoretical computer science, including probability, linear algebra and spectral methods.
Keep in mind: It assumes comfort with proofs and undergraduate mathematics; it is not a first course.
Open official resourceFormal proofs
Formal methods are central to several AI-for-mathematics examples. These tutorials teach the tooling; they do not certify that an AI system solved the wider problem in a headline.
Lean Project
Learn how to write definitions and proofs in Lean 4, a proof assistant used for machine-checked mathematics and formal verification.
Keep in mind: You need to install and run Lean. A checked example does not validate a different theorem or its informal headline.
Open official resourceLean Community
A hands-on tutorial for formalising mathematics with Lean and mathlib, with examples and exercises.
Keep in mind: A learning resource does not replace expert review of the formal statement or the human-readable claim.
Open official resourceSuggested order
You do not have to use every resource. Pick one from each stage and move on when you can explain the main ideas without copying a definition.
Use the mathematics and algorithms foundations until definitions, examples and proof steps stop feeling like a foreign language.
Study an introduction to theoretical computer science or a proof-based course. Focus on what a model of computation is and what a complexity claim actually says.
Work through Lean exercises. Save, reproduce and inspect the proof instead of trusting a polished explanation.
Ask which part of the workflow changed, what checked the result and whether the headline matches the formal statement.
Selection standard
The list is intentionally small. It favours primary provider pages and materials that teach a complete sequence rather than isolated tips.
Use what you learned