Awesome Theoretical Computer Science
The interdisciplinary of Mathematics and Computer Science; It is
distinguished by its emphasis on mathemtical technique and rigour.
Contents
Introductory Theoretical Computer Science
Broad Intros
Books
Lecture Videos Playlists
-
O’Donnell. CS Theory Toolkit
- It covers a large number of the math/CS topics that you need to know
for reading and doing research in Computer Science Theory.
Lecture Notes
-
Zhou. A Theorist’s Toolkit
- It covers a large number of the math/CS topics that you need to know
for reading and doing research in Computer Science Theory.
-
O’Donnell. A Theorist’s Toolkit
- It covers a large number of the math/CS topics that you need to know
for reading and doing research in Computer Science Theory.
-
Arora. Thinking Like a Theorist
- It covers a large number of the math/CS topics that you need to know
for reading and doing research in Computer Science Theory.
Automata, Computability, & Complexity
Lecture Notes
Lecture Videos Playlists
MOOC
Books
Puzzles and Problem Sets
Theoretical Computer Science Handbooks
Computational Complexity
General
Lecture Videos Playlists
-
O’Donnell. Undergrad Complexity Theory. Fall 2019 (15-455)
- Undergraduate course on computational complexity theory; It follows
the same spirit of Sipser’s part III.
-
O’Donnell. Graduate Complexity Theory
- It covers most of what is believed to be known to get started in
complexity theory research. #### Lecture Notes
-
Rudich & Wigderson. Computational Complexity Theory
- Three weeks of lectures from the IAS/Park City Mathematics Institute
Summer School on computational complexity. Topics include reductions,
lower-bounds, average-case complexity, randomness, interactive proof
systems, probabilistically checkable proofs, quantum computing, and
proof complexity. #### Books
-
Arora & Barak. Computational Complexity: A Modern Approach
- A golden standard textbook, Surveying computational complexity theory
for graduate students and researchers.
-
Goldreich. Computational Complexity: A Conceptual Perspective
- A grad introduction to computation complexity theory, emphasizing the
idea behind concepts of complexity theory.
-
Goldreich. P, NP, and NP-Completeness: The Basics of Computational
Complexity
- A very gentle introduction to some fundamental ideas of computational
complexity like NP-completeness and P vs NP.
-
Ogihara & Hemaspaandra. The Complexity Theory Companion
- An accessible, algorithmically oriented, research-centered, up-to-date
guide to some of the most interesting techniques of complexity theory.
-
Papadimitriou. Computational Complexity
- Body of knowledge for studying the performance and limitations of
computer algorithms. Among topics covered are: reductions and
NP-completeness, cryptography and protocols, randomized algorithms, and
approximability of optimization problems, circuit complexity, the
“structural” aspects of the P=NP question, parallel computation, and the
polynomial hierarchy. #### Popular Science
-
Fortnow. The Golden Ticket: P, NP, and the Search for the
Impossible
- A nontechnical introduction to P-NP, its rich history, and its
algorithmic implications for everything we do with computers and beyond.
-
Aaronson. Quantum Computing Since Democritus
- It covers an amazing array of topics. Beginning in antiquity
withDemocritus, it progresses through logic and set theory,computability
and complexity theory, quantum computing, cryptography, the information
content of quantum states, and theinterpretation of quantum mechanics.
Communication Complexity
Books
Circuit Complexity
Books
Randomization
General
Algorithms
Lecture Video Playlists
Logic and Foundational Mathematics
Computability Theory
Books
Introductory
-
Cutland. Computability: An Introduction to Recursive Function
Theory
- Intuitively, It explains the idea of a computable function: a function
whose values can be calculated in an effective or automatic way.
-
Cooper. Computability Theory
- A concise, comprehensive, and authoritative introduction to
contemporary computability theory, techniques, and results.
-
Davis. Computability and Unsolvability
- In this classic text, Dr. Davis provides a clear introduction to
computability, at an advanced undergraduate level, that serves the needs
of specialists and non-specialists alike. ##### Collected Papers
-
Copeland, Posy & Shagrir (editors). Computability: Turing, Gödel,
Church, and Beyond
- Computer scientists, mathematicians, and philosophers discuss the
conceptual foundations of the notion of computability as well as recent
theoretical developments. ##### Popular Science
-
Papadimitriou. Turing: A Novel About Computation
- The world of computation according to Turing, an interactive tutoring
program, as told to star-crossed lovers: a novel.
-
Petzold. The Annotated Turing: A Guided Tour Through Alan Turing’s
Historic Paper on Computability and the Turing Machine
- A Guided Tour through Alan Turing’s Historic Paper on Computability
and the Turing Machine. ##### Advanced
-
Soare. Recursively Enumerable Sets and Degree
- It gives a complete account of the theory of r.e degrees. The
definitions, results and proofs are always clearly motivated and
explained before the formal presentation; the proofs are described with
remarkable clarity and conciseness.
-
Odifreddi. Classical Recursion Theory: The Theory of Functions and
Sets of Natural Numbers
- An impressive presentation of classical recursion theory. It is highly
recommended to everyone interested in recursion theory.
Computational Complexity
Books
Philosophy
Lecture Notes
Popular Science
Papers
Physics
Books
Math/Logic Preliminaries
General
Lecture Video Playlist
-
Lehman, Leighton & Meyer. Mathematics for Computer Science
- An introduction to discrete mathematics oriented toward computer
science and engineering.
-
Knuth, Graham & Patashnik. Concrete Mathematics: A Foundation for
Computer Science
- An expansion of the Mathematical Preliminaries section in Knuth’s
classic Art of Computer Programming, but the style of presentation is
more leisurely, and individual topics are covered more deeply.
-
Aho & Ullman. Foundations of Computer Science
- A classic math-oriented introduction to computer science.
-
Tu Delft. Delftse Foundations of Computation
- A textbook for a one quarter introductory course in theoretical
computer science.
-
Comprehensive Mathematics for Computer Scientists
- A series dedicated to math topics and their relevance to computer
science.
-
Krantz. Handbook of Logic and Proof Techniques for Computer
Science
- A concise offered as an accessible reference on mathematical logic for
the professional computer scientist.
-
Makinson. Sets, Logic and Maths for Computing
- It presents a careful selection of the material most needed by
students in their first two years studying computer science.
-
Yves Nievergelt. Logic, Mathematics, and Computer Science: Modern
Foundations with Practical Applications
- For lower undergraduates, It introduces the reader to logic, proofs,
sets, and number theory, Focusing on foundations. It provides complete
details and derivations of formal proofs.
-
Ayala-Rincón & Moura. Applied Logic for Computer Scientists:
Computational Deduction and Formal Proofs
- An introduction to logic as a basis for any deductive computational
framework. It contains special chapters for certifying the robustness of
software and hardware systems
-
Ben-Ari. Mathematical Logic for Computer Science
- Semantic tableaux are used because they are theoretically sound and
easy to understand.
-
Jeremy Kun. A Programmer’s Introduction to Mathematics
- Uses your familiarity with ideas from programming and software to
teach mathematics.
-
Vince. Foundation Mathematics for Computer Science: A Visual
Approach
- A range of mathematical topics to provide a solid foundation for an
undergraduate course in computer science, starting with a review of
number systems and their relevance to digital computers, and finishing
with differential and integral calculus.
-
Oberguggenberger & Ostermann. Analysis for Computer Scientists:
Foundations, Methods, and Algorithms
- Presents an algorithmic approach to mathematical analysis, with a
focus on modelling and on the applications of analysis. #### Lecture
Notes
-
Maciej Paluszynski. Calculus for Computer Scientists
- calculus lecture notes taught for undergrad computer science students
### Transition To Pure Rigour Math It is already curated
here
- Introductory proofs and mathematical maturity.
Discrete Mathematics
Lecture Notes
Books
MOOC
Surveys
Other Resources
Blog Posts and Essays
-
Omer Reingold. The Practice of Theory Research
- A research methods course, concentrating on the how rather than the
what. It focuses on research practices common for computer science
theory research.
-
Omer Reingold. TOC: a Personal Perspective (2021)
- In celebration of 25 years for “TOC: a Scientific Perspective (1996),”
by Oded Goldreich and Avi Wigderson. It spots the light on a criticism
directed to TCS, that it is not as deep as Math and not as useful as CS.
-
Blum. You and Your Research: An Advice to a Beginning Graduate
Student
- Manuel Blum, A very popular figure in TCS, gives research advices for
juniors.
-
Dijkstra. The Three Golden Rules for Successful Scientific
Research
- A note devoted to three rules that must be followed if you want to be
successful in scientific research.
-
Goldreich. Essays and Opinions
- Personal Essays by Oded Goldreich. They are very unique in their
conceptual message of TCS and its community.
-
Barak. Advice for The Budding Theorist
- Tips for anyone interested in theoretical computer science.
-
Barak. Surveys For Students
- Surveys for high-school, undergraduate, and even researchers.
-
Barak. Non-technical or Less-technical Writings and Talks
- Posts oriented more for a less-technically matured audience.
-
Karp. A Personal View of Computer Science at Berkeley
- Karp addresses: In 1968 computer science at Berkeley was problematic,
with two departments working independently to develop programs, and his
personal reflections.
-
Hamming. You and Your Research
- Why do so few scientists make significant contributions and so many
are forgotten in the long run? The talk is about what Hamming has
learned.
-
Weinberg. Four Golden Lessons
- Lessons for students and researchers given by Steven Weinberg.
-
Terry. Career Advice
- A collection of various pieces of advice on academic career issues in
mathematics, roughly arranged by the stage of career at which the advice
is most pertinent.
Magazines/Journals/News
Popular Science
Cheat-Sheets
-
TCS Cheat Sheet
- A sheet of notes containing essential toolboxes needed by any
theoretical computer scientist.
Talks
-
TCS+ - A
series of online seminars in theoretical computer science. The goal is
to make engaging talks accessible to the widest possible audience.
-
Turing Lectures. ACM
-
ACM A.M. Turing Laureate Interview. Berkeley - Interviews with
Berkeley’s Turing award winners.
-
Berkeley in the 80s - Interviews with eminent figures in Berkeley’s
theoretical computer science.
-
Berkeley’s Public Lectures
- Programs, Events, and workshops, that aim toward maximizing impact and
engagement across the theoretical computer science community.
Useful Links