User Experience on mobile might not be great yet, but I'm working on it.

Your first time on this page? Allow me to give some explanations.

Awesome Theoretical Computer Science

The interdicplinary of Mathematics and Computer Science, Distinguisehed by its emphasis on mathemtical technique and rigour.

Here you can see meta information about this topic like the time we last updated this page, the original creator of the awesome list and a link to the original GitHub repository.

Last Update: Jan. 17, 2022, 3:22 p.m.
Thank you mostafatouny & contributors
View Topic on GitHub:
mostafatouny/awesome-theoretical-computer-science

Search for resources by name or description.
Simply type in what you are looking for and the results will be filtered on the fly.

Further filter the resources on this page by type (repository/other resource), number of stars on GitHub and time of last commit in months.

Books

Moore & Mertens. The Nature of Computation

http://nature-of-computation.org/

Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science

https://www.math.ias.edu/files/Book-online-A…

Lecture Videos Playlists

O'Donnell. CS Theory Toolkit

https://www.youtube.com/playlist?list=PLm3J0…

bilibili

https://www.bilibili.com/video/BV1Ry4y1e7zR

Lecture Notes

Zhou. A Theorist's Toolkit

https://yuanz.web.illinois.edu/teaching/B609…

O'Donnell. A Theorist's Toolkit

https://www.cs.cmu.edu/~odonnell/toolkit13/

Arora. Thinking Like a Theorist

https://www.cs.princeton.edu/courses/archive…

Lecture Notes

Watrous. Introduction to The Theory of Computing

https://cs.uwaterloo.ca/~watrous/ToC-notes/

Lecture Videos Playlists

Yanofsky. Theoretical Computer Science

https://www.youtube.com/playlist?list=PLCqUs…

O'Donnell. Great Ideas in Theoretical Computer Science. CMU

https://www.youtube.com/playlist?list=PLm3J0…

MOOC

Intro to Theoretical Computer Science

https://www.udacity.com/course/intro-to-theo…

Computability, Complexity & Algorithms. Georgia Institute of Technology

https://www.udacity.com/course/computability…

Books

Michael Sipser. Introduciton to Theory of Computation

https://www.cengage.com/c/introduction-to-th…

Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation

https://www.pearson.com/us/higher-education/…

Barak. Introduction to TCS

https://introtcs.org/public/index.html

Puzzles and Problem Sets

Zhu & Ko. Problem Solving in Automata, Languages, and Complexity

https://onlinelibrary.wiley.com/doi/book/10.…

Theoretical Computer Science Handbooks

Atallah & Blanton. Algorithms and Theory of Computation Handbook: General Concepts and Techniques

https://www.routledge.com/Algorithms-and-The…

Atallah & Blanton. Algorithms and Theory of Computation Handbook: Special Topics and Techniques

https://www.routledge.com/Algorithms-and-The…

Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity

https://mitpress.mit.edu/books/handbook-theo…

Handbook of Theoretical Computer Science. Volume B: Formal Methods and Semantics

https://mitpress.mit.edu/books/handbook-theo…

Lecture Videos Playlists

O'Donnell. Undergrad Complexity Theory. Fall 2019 (15-455)

https://www.youtube.com/playlist?list=PLm3J0…

O'Donnell. Graduate Complexity Theory

https://www.youtube.com/playlist?list=PLm3J0…

Lecture Notes

Rudich & Wigderson. Computational Complexity Theory

http://www.ams.org/books/pcms/010/

Books

Arora & Barak. Computational Complexity: A Modern Approach

https://theory.cs.princeton.edu/complexity/b…

Goldreich. Computational Complexity: A Conceptual Perspective

http://www.wisdom.weizmann.ac.il/~oded/cc-bo…

Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity

http://www.wisdom.weizmann.ac.il/~oded/bc-bo…

Ogihara & Hemaspaandra. The Complexity Theory Companion

https://www.springer.com/gp/book/97835406741…

Papadimitriou. Computational Complexity

https://www.pearson.com/us/higher-education/…

Popular Science

Fortnow. The Golden Ticket: P, NP, and the Search for the Impossible

https://goldenticket.fortnow.com

Aaronson. Quantum Computing Since Democritus

https://assets.cambridge.org/97805211/99568/…

Books

Rao & Yehudayoff. Communication Complexity and Applications

https://www.cambridge.org/core/books/communi…

Books

Jukna. Boolean Function Complexity: Advances and Frontiers

https://www.springer.com/gp/book/97836422450…

Clote & Kranakis. Boolean Functions and Computation Models

https://www.springer.com/gp/book/97835405943…

General

Goldreich. Randomized Methods in Computation

http://www.wisdom.weizmann.ac.il/~oded/rnd.h…

Lecture Video Playlists

Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs

https://ocw.mit.edu/courses/electrical-engin…

Books

Demaine. Games, Puzzles, and Computation

https://www.routledge.com/Games-Puzzles-and-…

Knuth. The Art of Computer Programming

https://en.wikipedia.org/wiki/The_Art_of_Com…

Introductory

Cutland. Computability: An Introduction to Recursive Function Theory

https://www.cambridge.org/highereducation/bo…

Cooper. Computability Theory

https://www.routledge.com/Computability-Theo…

Davis. Computability and Unsolvability

https://www.amazon.com/Computability-Unsolva…

Collected Papers

Copeland, Posy & Shagrir (editors). Computability: Turing, Gödel, Church, and Beyond

https://mitpress.mit.edu/books/computability

Popular Science

Papadimitriou. Turing: A Novel About Computation

https://mitpress.mit.edu/books/turing-novel-…

Petzold. The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

http://www.charlespetzold.com/AnnotatedTurin…

Advanced

Soare. Recursively Enumerable Sets and Degree

https://www.springer.com/gp/book/97835406668…

Odifreddi. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers

https://archive.org/details/classicalrecursi…

Books

Pudlák. Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction

https://www.springer.com/gp/book/97833190011…

Lecture Notes

6.893 Philosophy and Theoretical Computer Science. MIT

https://stellar.mit.edu/S/course/6/fa11/6.89…

Books

Knuth. Things a Computer Scientist Rarely Talks About

https://web.stanford.edu/group/cslipublicati…

Floyd & Bokulich. Philosophical Explorations of the Legacy of Alan Turing: Turing 100

https://www.springer.com/gp/book/97833195327…

Popular Science

Deutsch. The Fabric of Reality: The Science of Parallel Universes and Its Implications

http://www.daviddeutsch.org.uk/books/the-fab…

Papers

Aaronson. Why Should Philosophers Care About Computational Complexity Theory

https://www.scottaaronson.com/papers/philos.…

Aharonov & Vazirani, Is Quantum Mechanics Falsifiable? A Computational Perspective on the Foundations of Quantum Mechanics

https://www.researchgate.net/publication/227…

Walter Dean. Computational Complexity Theory and the Philosophy of Mathematics

https://academic.oup.com/philmat/article/27/…

Stanford Encyclopedia of Philosophy. Computational Complexity Theory

https://plato.stanford.edu/entries/computati…

Books

Feynman. Feynman And Computation: Exploring The Limits Of Computers

https://www.taylorfrancis.com/books/feynman-…

here

https://arxiv.org/abs/2106.10522

Monographs

Leonard Susskind. Three Lectures on Complexity and Black Holes

https://link.springer.com/book/10.1007/978-3…

Lecture Video Playlist

Lehman, Leighton & Meyer. Mathematics for Computer Science

https://ocw.mit.edu/courses/electrical-engin…

Companion Textbook

https://ocw.mit.edu/courses/electrical-engin…

Books

Knuth, Graham & Patashnik. Concrete Mathematics: A Foundation for Computer Science

https://www.pearson.com/us/higher-education/…

Aho & Ullman. Foundations of Computer Science

http://i.stanford.edu/~ullman/focs.html

Tu Delft. Delftse Foundations of Computation

https://textbooks.open.tudelft.nl/textbooks/…

Comprehensive Mathematics for Computer Scientists

https://www.springer.com/series/5517

Krantz. Handbook of Logic and Proof Techniques for Computer Science

https://www.maa.org/press/maa-reviews/handbo…

Makinson. Sets, Logic and Maths for Computing

https://www.springer.com/gp/book/97830304221…

Yves Nievergelt. Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications

https://www.springer.com/gp/book/97814939322…

Ayala-Rincón & Moura. Applied Logic for Computer Scientists: Computational Deduction and Formal Proofs

https://www.springer.com/gp/book/97833195165…

Ben-Ari. Mathematical Logic for Computer Science

https://www.springer.com/gp/book/97814471412…

Jeremy Kun. A Programmer's Introduction to Mathematics

https://pimbook.org/

Vince. Foundation Mathematics for Computer Science: A Visual Approach

https://www.springer.com/gp/book/97830304207…

Oberguggenberger & Ostermann. Analysis for Computer Scientists: Foundations, Methods, and Algorithms

https://www.springer.com/gp/book/97833199115…

Lecture Notes

Maciej Paluszynski. Calculus for Computer Scientists

https://www.math.uni.wroc.pl/~mpal/academic/…

Lecture Notes

Halpern. CS 2802: Discrete Structures - Honors. 2020. Cornell

https://www.cs.cornell.edu/courses/cs2802/20…

Homework

https://www.cs.cornell.edu/courses/cs2802/20…

Books

Rosen. Discrete Mathematics and Its Applications

https://www.mheducation.com/highered/product…

Rosen. Handbook of Discrete and Combinatorial Mathematics

https://www.taylorfrancis.com/books/handbook…

Rosenberg & Trystram. Understand Mathematics, Understand Computing: Discrete Mathematics That All Computing Students Should Know

https://www.springer.com/gp/book/97830305837…

Gries & Schneider. A Logical Approach to Discrete Math

https://www.springer.com/gp/book/97803879411…

Mariconda & Tonolo. Discrete Calculus: Methods for Counting

https://www.springer.com/gp/book/97833190303…

MOOC

Introduction to Discrete Mathematics for Computer Science. UC San-Diego

https://www.coursera.org/specializations/dis…

Surveys

Watrous. Quantum Computational Complexity

https://arxiv.org/abs/0804.3401

Harrow & Ashley Montanaro. Quantum Computational Supremacy

https://www.nature.com/articles/nature23458

Cook. An Overview of Computational Complexity

https://dl.acm.org/doi/abs/10.1145/1283920.1…

Fortnow & Homer. A Short History of Computational Complexity

https://www.researchgate.net/profile/Lance-F…

Goldreich. Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali

http://www.wisdom.weizmann.ac.il/~oded/sst.h…

Blog Posts and Essays

Omer Reingold. The Practice of Theory Research

https://omereingold.wordpress.com/cs-163-the…

Omer Reingold. TOC: a Personal Perspective (2021)

https://theorydish.blog/2021/04/15/toc-a-per…

Blum. You and Your Research: An Advice to a Beginning Graduate Student

https://www.cs.cmu.edu/~mblum/research/pdf/g…

Dijkstra. The Three Golden Rules for Successful Scientific Research

https://link.springer.com/chapter/10.1007%2F…

Goldreich. Essays and Opinions

http://www.wisdom.weizmann.ac.il/~oded/essay…

Barak. Advice for The Budding Theorist

https://windowsontheory.org/2015/11/03/advic…

Barak. Surveys For Students

https://thmatters.wordpress.com/surveys/

Barak. Non-technical or Less-technical Writings and Talks

https://www.boazbarak.org/informal/

Karp. A Personal View of Computer Science at Berkeley

https://www2.eecs.berkeley.edu/bears/CS_Anni…

Hamming. You and Your Research

https://www.cs.virginia.edu/~robins/YouAndYo…

Weinberg. Four Golden Lessons

https://www.nature.com/articles/426389a

Terry. Career Advice

https://terrytao.wordpress.com/career-advice/

Magazines/Journals/News

The Legacy of Alan Turing: Pushing the Boundaries of Computation (Volume 18, Issue 3, Spring 2012). ACM, XRDS

https://dl.acm.org/toc/xrds/2012/18/3

SIGACT News

https://dl.acm.org/loi/sigact

Foundations and Trends in Theoretical Computer Science

https://www.nowpublishers.com/TCS

Popular Science

Shasha & Lazere. Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists

https://www.springer.com/gp/book/97803879826…

Cheat-Sheets

TCS Cheat Sheet

https://www.cosy.sbg.ac.at/~held/teaching/aa…

Talks

TCS+

https://www.youtube.com/user/TCSplusSeminars

Oxford-Warwick Complexity Meetings

https://www.dcs.warwick.ac.uk/~igorcarb/comp…

Turing Lectures. ACM

https://amturing.acm.org/lectures.cfm

Shafi Goldwasser and Silvio Micali

https://www.youtube.com/watch?v=yBRbSzPgG4A

Shafi Goldwasser

https://www.youtube.com/watch?v=7D4hIe7M4qU&…

Simons' Public Lectures

https://simons.berkeley.edu/programs

Simons' Theory Shorts

https://www.youtube.com/playlist?list=PLgKuh…

1

2

https://www.youtube.com/watch?v=2BdBfsXbST8

Silvio Micali

https://www.youtube.com/watch?v=zNdhgOk4-fE

Richard Karp

https://www.youtube.com/watch?v=KllCrlfLuzs

1

2

https://www.youtube.com/watch?v=uX5t8EivCaM

Computational Complexity

https://www.youtube.com/channel/UCzBw287tly0…

Related Awesome Lists

tayllan/awesome-algorithms

A curated list of awesome places to learn and/or practice algorithms.

10.75K
1.94K
6m
n/a

rossant/awesome-math

A curated list of awesome mathematics resources

4.91K
694
77d
n/a

sobolevn/awesome-cryptography

A curated list of cryptography resources and links.

3.38K
459
75d
n/a

desireevl/awesome-quantum-computing

A curated list of awesome quantum computing learning and developing resources.

1.56K
292
74d
n/a

Useful Links

Theory of Computing Blog Aggregator

https://cstheory-feed.org/

Rubinstein & Weinberg. Research Masters in TCS

https://www.cs.princeton.edu/~smattw/masters…

Barak. Research Masters in TCS

https://docs.google.com/spreadsheets/d/1znVm…

Conferences in TCS

http://www.nicolas-hermann.net/conf.html

CS Theory Events Aggregator

https://cstheory-events.org/

List of TCS Conferences and Workshops

https://cstheory.blogoverflow.com/theoretica…

Theory Announcements

https://dmatheorynet.blogspot.com/

PolyTCS

https://polytcs.wordpress.com/

Complexity Network

https://sites.google.com/view/complexitynetw…

SIGACT

https://www.sigact.org/articles/web_pages.ht…

TCS Stack Exchange

https://cstheory.stackexchange.com/

TCS Subreddit

https://www.reddit.com/r/theoreticalcs