awesome-theoretical-computer-science

TCS resource hub

An extensive collection of resources and lecture materials on theoretical computer science for learning and reference

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

GitHub
707 stars
12 watching
44 forks
Language: Python
last commit: 16 days ago
Linked from 4 awesome lists

awesomeawesome-listcomputer-sciencelistlistsmathematicstheoretical-computer-sciencetheory-of-computation

Broad Intros / Lecture Notes
Barak. Introduction to TCS A modern, brief, and accessible text which introduces theoretical computer science for undergrads. It includes topics not usually included in standard undergrad text-books

Broad Intros / Lecture Videos Playlists
Yanofsky. Theoretical Computer Science undergrad introduction to theory of computation
Anil Ada. Great Ideas in Theoretical Computer Science. CMU A series of lectures on selected notable topics in theoretical computer science
O'Donnell. Great Ideas in Theoretical Computer Science. CMU A series of lectures on selected notable topics in theoretical computer science

Broad Intros / Books
Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science A sweeping survey of complexity theory, emphasizing the field’s insights and challenges. It explains the ideas and motivations leading to key models, notions, and results
Moore & Mertens. The Nature of Computation It spans complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and of quantum computing. It provides accessible explanations

Broad Intros / Handbooks
Atallah & Blanton. Algorithms and Theory of Computation Handbook: General Concepts and Techniques A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science
Atallah & Blanton. Algorithms and Theory of Computation Handbook: Special Topics and Techniques A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science
Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science
Handbook of Theoretical Computer Science. Volume B: Formal Methods and Semantics A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science

Theory of Computation / Introductory / Lecture Notes
Watrous. Introduction to The Theory of Computing undergrad introduction to theory of computation

Theory of Computation / Introductory / MOOC
Intro to Theoretical Computer Science It teaches basic concepts in theoretical computer science, such as NP-completeness, and what they imply for solving tough algorithmic problems
Computability, Complexity & Algorithms. Georgia Institute of Technology It focuses on the big fundamental questions of computing, and how understanding the power and limitations of algorithms helps us develop the tools to make real-world computers smarter, faster and safer

Theory of Computation / Introductory / Books
Sipser. Introduction to Theory of Computation A standard text for introducing theory of computation for undergrads
Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation Introductory undergrad textbook for automata, languages and theory of computation topics

Theory of Computation / Introductory / Puzzles and Problem Sets
Zhu & Ko. Problem Solving in Automata, Languages, and Complexity A problem-set text for automata, languages, and complexity

Theory of Computation / Computational Complexity / Introductory
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
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
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

Theory of Computation / Computational Complexity / Communication Complexity
Mark Bun. CS591 Communication Complexity A graduate course which introduces the fundamental results and techniques in the area and some research frontier questions. Themes include: Communication models and the communication complexity zoo, Information vs. communication, Query-to-communication lifting, and Applications
Rao & Yehudayoff. Communication Complexity and Applications An excellent and very readable introductory textbook to the field of communication complexity

Theory of Computation / Computational Complexity / Circuit Complexity
Jukna. Boolean Function Complexity: Advances and Frontiers A modern textbook surveying circuit complexity
Clote & Kranakis. Boolean Functions and Computation Models An introduction to circuit complexity, boolean functions, and computation models

Theory of Computation / Computational Complexity / Quantum Complexity
Uni Paderborn. Quantum Complexity Theory. Winter 2020 CS Masters level lectures on topics including Boson sampling, quantum interactive proofs, and quantum merlin arthur
Henry Yuen. The Complexity of Entanglement. Fall 2020 Focuses on cutting edge topics in quantum information that relate to Complexity of Entanglement. - see this also

Theory of Computation / Computational Complexity / Proof Complexity
Robert Robere. Proof Complexity: Algorithms and Lower Bounds An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization

Theory of Computation / Computability Theory / Books
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
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
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

Logic / Computational Complexity / Books
Pudlák. Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction Presents a wide range of results in logic and computational complexity

Programming Language Theory / Basics / Books
MIT OCW Structure and Interpretation of Computer Programs - , , , , , - Fundamental principles of computer programming in Scheme, including recursion, abstraction, modularity, and programming language design and implementation

Programming Language Theory / Introductory / Books
Pierce. Software Foundations. Pennsylvania A broad introduction series to the mathematical underpinnings of reliable software. It's composed of proof scripts for the Coq proof assistant. It's is intended for a broad range of readers, With no specific background assumed

Programming Language Theory / Formal Verification / Lecture Notes
UW CSE505 18au Principles of PL Techniques for thinking crisply about programming languages, write some fascinating programs, and discuss various design tradeoffs

Programming Language Theory / Formal Verification / Books
Chlipala. Formal Reasoning About Programs A book introducing both machine-checked proof with Coq Proof Assistant and approaches to formal reasoning about program correctness
Lean Proof Assistant Lean Proof Assistant

Programming Language Theory / Type Theory / Lecture Notes
Martin-Löf. Intuitionistic Type Theory Notes by Giovanni Sambin of a series of type theory lectures given in Padua, June 1980

Programming Language Theory / Type Theory / Books
Bengt. Programming in Martin-Löf's Type Theory This book describes different type theories (theories of types, polymorphic and monomorphic sets, and subsets) from a computing science perspective
The Univalent Foundations Program Institute for Advanced Study. Homotopy Type Theory: Univalent Foundations of Mathematics The present book is intended as a first systematic exposition of the basics of univalent foundations, and a collection of examples of this new style of reasoning — but without requiring the reader to know or learn any formal logic, or to use any computer proof assistant

Programming Language Theory / Functional Programming / Lecture Notes
Helsinki. Haskell MOOC An online course on functional programming with Haskell programming language, and a live interactive Telegram community
Cornell. Functional Programming in Ocaml A modern course on data structures and functional programming using OCaml

Algorithms / General / Lecture Notes
Erik Demaine. Advanced Data Structures. MIT It covers major results and current directions of research in data structure
Arora. Advanced Algorithm Design Notably uses ideas such as randomness, approximation, high dimensional geometry. Faces uncertainty, approaches to handle big data, handling intractability, heuristic approaches, ..etc

Algorithms / General / Books
Knuth. The Art of Computer Programming A legendary series by Donald Knuth on design and analysis of algorithms

Algorithms / Lower Bounds / Lecture Videos Playlists
Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs A class taking a practical approach to proving problems can't be solved efficient

Algorithms / Lower Bounds / Books
Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds A sequel to Garey and Johnson's Computers and Intractability: A Guide to NP-Completeness. New topics include Parameterized Complexity, Lower bounds on approximation, Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), Online Algorithms, Streaming Algorithms, Polynomial Parity Arguments, and Parallelism
Demaine. Games, Puzzles, and Computation It shows that games and puzzles can serve as powerful models of computation, Offering a new way of thinking about computation

Algorithms / Randomization & Probability / Lecture Notes
Mary Wootters. Randomized Algorithms and Probabilistic Analysis. Stanford Key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though applications will be discussed in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, and random walks
Koutsoupias. Probability and Computing. Oxford Introduction to probabilistic methods in computer science
First Harvey. and Course in Randomized Algorithms. Columbia. - Respectively, undergrad and grad courses for probabilistic methods in algorithms
Lee. Randomized Algorithms and Probabilistic Analysis. Washington. Topics include Discrete probability, High-dimensional geometry and statistics, Information and entropy, and Markov chains and convergence to equilibrium
Aspnes. Notes on Randomized Algorithms Supplemental notes to the standard books by Mitzenmacher & Upfals, and Motwani & Raghavan

Algorithms / Approximation / Lecture Notes
Chekuri. Approximation Algorithmis Illinois A broad introduction to results and techniques with an emphasis on fundamental problems and widely applicable tools. Also more advanced and specialized topics
Dinitz. Approximation Algorithms. Johns Hopkins It includes greedy, local search, dynamic programming, randomized rounding, tree embeddings, and semidefinite programming
Gupta & Ravi. Approximation Algorithms. CMU It includes convex programming-based, randomness, and metric methods

Algorithms / Approximation / Books
Williamson & Shmoys. The Design of Approximation Algorithms It includes greedy, local search algorithms, dynamic programming, linear and semidefinite programming, and randomization
Du & Ko. Design and Analysis of Approximation Algorithms A technique-oriented approach provides a unified view. It includes detailed algorithms, proofs, analyses, examples, and applications from research papers
Vijay Vazirani. Approximation Algorithms

Algorithms / Parameterized / Lecture Videos Playlist
Parametarized Algorithms by Warsaw

Algorithms / Learning-augmented / Lecture Notes
Indyk & Daskalakis. Learning-augmented Algorithms. MIT

Algorithms / Learning-augmented / Big List
Algorithms with Predictions

Information/Coding Theory / Lecture Notes
Madhu Sudan. Essential Coding Theory Some elements of Algorithmic tasks of encoding and decoding and its connections with error-correction; These codes are now tools in the design and analysis of algorithms, and also in many aspects of computational complexity. The focus is on constructions of algorithmic and asymptotic importance. Requires only basic mathematical maturity
Part I Scott Aaronson. Quantum Information Science. & - Part I: Presuppose only linear algebra and a bit of classical algorithms. Topics include quantum circuits, density matrices, entanglement entropy, Wiesner’s quantum money, QKD, quantum teleportation, the Bell inequality, interpretations of QM, the Shor 9-qubit code, and the algorithms of Deutsch-Jozsa, Bernstein-Vazirani, Simon, Shor, and Grover. Part II: Perspectives on quantum computing that go beyond the bare quantum circuit model, like Hamiltonians, Stabilizer formalism, Bosons and Fermions, Cluster states, and Matrix product states

Information/Coding Theory / Workshops
Simons Institute. Information Theory Program It aims to strengthen the ties between computation and communication communities. It explores (1) information theoretic techniques in complexity theory and combinatorics, (2) Coding theory and applications, and (3) information theory, machine learning, and big data

Information/Coding Theory / Conferences
Compression+Computation 2022 It bridges the gap of Theoretical Computer Science and Bioinformatics communities, On new data compression techniques, and computation over compressed data

Cryptography / Books
Lindell. Tutorials on the Foundations of Cryptography Advanced tutorials appropriate for self-study by experienced researchers,
Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness An introduction to the interwoven domains of cryptography, proofs and randomness
Goldreich. Randomized Methods in Computation The aim of the current course is to make the students familiar with some of randomized methods

Machine Learning Theory / Lecture Notes
Blum. An Introduction to the Theory of Machine Learning. TTIC The basic theory underlying machine learning and the process of generalizing from data
Telgarsky. Deep Learning Theory. Illinois Focuses on simplified proofs over what appears in the literature, and classical perspective of achieving a low test error for binary classification with IID data via standard (typically ReLU) feedforward networks
Vaughan. CS260: Machine Learning Theory A broad overview of the theoretical foundations underlying common machine learning algorithms
Livni. COS 511 Theoretical Machine Learning. Princeton Formally define and study various models that have been proposed for learning. The course will present and contrast the statistical, computational and online models for learning. We will present and rigorously analyze some of the most successful algorithms in machine learning that are extensively used today
Moitra. Theoretical Foundations for Deep Learning. MIT It explores theoretical foundations for deep learning, emphasizing the following themes: (1) Approximation: What sorts of functions can be represented by deep networks, and does depth provably increase the expressive power? (2) Optimization: Essentially all optimization problems we want to solve in practice are non-convex. What frameworks can be used to analyze such problems? (3) Beyond-Worst Case Analysis: Deep networks can memorize worst-case data, so why do they generalize well on real-world data?
Arora. Overcoming Intractability in Machine Learning A seminar course that will focus on the following phenomenon: many problems in machine learning are formally intractable (e.g., NP-hard). Nevertheless they are solved in practice by heuristics. Can we design algorithms with provable guarantees (running time, solution quality)?

Machine Learning Theory / Books
Vazirani & Kearns. An Introduction to Computational Learning Theory Emphasizing issues of computational efficiency, It introduces a number of central topics in computational learning theory
Shalev-Shwartz. Understanding Machine Learning: From Theory to Algorithms It provides an extensive theoretical account of the fundamental ideas underlying machine learning and the mathematical derivations that transform these principles into practical algorithms

Machine Learning Theory / Workshops
Simons Institute. Foundations of Deep Learning Program Aligning and focusing theoretical and applied researchers on the common purpose of building empirically relevant theoretical foundations of deep learning. Specifically, the intention was to identify and make progress on challenges that, on one hand, are key to guiding the real-world use of deep learning and, on the other hand, can be approached using theoretical methodology
Simons Institute. Foundations of Data Science Identifying a set of core techniques and principles that form a foundation for the subject
Foundations of Machine Learning Aims to grow the reach and impact of computer science theory within machine learning
Toward Theoretical Understanding of Deep Learning
A Brief Introduction to Theoretical Foundations of Machine Learning and Machine Teaching Formal methods and machine learning can inform each other from deductive and inductive reasoning perspectives. This talk aims to facilitate the dialogue between the two communities by establishing some fundamental concepts in learning theory

Machine Learning Theory / Other
Blum. Intro Machine Learning Theory
Blum, et.al. Machine Learning, Game Theory, and Mechanism Design for a Networked World
Agrawal & Jaiswal. When Machine Learning Meets AI and Game Theory

Game Theory / Lecture Notes
Tim Roughgarden. Complexity Theory, Game Theory, and Economics: The Barbados Lectures A mini-course notes of two-fold goals: mini-course is twofold: (i) Explain how complexity theory has helped illuminate several barriers in economics and game theory; and (ii) Illustrate how game-theoretic questions have led to new and interesting complexity theory, including recent several breakthroughs
Eva Tardos. Algorithmic Game Theory It combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will study a range of topics at this interface. The only prerequisite to the course is mathematical thinking
Chekuri. Topics in Algorithms: Algorithmic Game Theory A broad graduate-level introduction to: auctions, existence and computation of equilibria in games and markets, algorithmic mechanism design, price of anarchy and price of stability, games relevant to networks and e-commerce. The emphasis will be on conceptual ideas and algorithmic aspects. No familiarity with game theory or economics will be assumed
Penna. Algorithmic Game Theory The course discusses algorithmic aspects of game theory, such as a general introduction to game theory, auctions, mechanisms, the costs of a central control optimum versus those of an equilibrium under selfish agents, and algorithms and complexity of computing equilibria
Brown. Resources list for game theory TAs based these notes in large part on the lecture notes and accompanying videos of Tim Roughgarden's CS 364A and CS 364B courses at Stanford, and Jason Hartline's Mechanism Design and Approximation textbook
Fang. Advanced Topics in Machine Learning and Game Theory A graduate-level course covering the topics at the intersection of machine learning and game theory
Xu. Topics in Learning and Game Theory A graduate level course covering topics at the interface between machine learning and game theory
Tim Roughgarden. Foundations of Blockchains The science and technology of blockchain protocols and the applications built on top of them, with an emphasis on fundamental principles rather than specific protocols. - See also

Game Theory / Books
Apt & Grädel. Lectures in Game Theory for Computer Scientists Games provide mathematical models for interaction, and numerous tasks in computer science can be formulated in game-theoretic terms
Eva Tardos & et.al. Algorithmic Game Theory Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on important game theory applications such as incentives and pricing, cost sharing, information markets and cryptography and security

Game Theory / Workshops
Simons Institute. Economics and Computation Program The intersection is motivated by applications such as large-scale digital auctions and markets, and fundamental questions such as the computational complexity of Nash equilibria and complexity and approximation in mechanism design. Also, To productively model and study the Internet and its novel computational phenomena, Models and insights can be gained from from game theory and economic theory. The computational point of view, on the other hand, is essential to understand a world in which markets are networked and the default platforms of economic transactions are algorithmic
Simons Institute. Learning and Games Program The intersection is manifested by (1) Data input to machine learning algorithms are generated by self-interested parties, (2) Machine learning is used to optimize economic systems or acts, (3) Machine learning models used in critical systems are becoming prone to adversarial attacks, and (4) Several machine learning approaches can be framed as finding the equilibrium of a game
Eva Tardos. Learning and Efficiency in Games How to quantify the impact of strategic user behavior on overall performance in games including traffic routing as well as online auctions

Math and Logic / General / Lecture Videos Playlist
Lehman, Leighton & Meyer. Mathematics for Computer Science An introduction to discrete mathematics oriented toward computer science and engineering. -

Math and Logic / General / Books
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
Lacona. LOGIC: Lecture Notes for Philosophy, Mathematics, and Computer Science Suitable for undergraduate introductions to logic and early graduate courses on logic
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

Math and Logic / General / Lecture Notes
Paluszynski. Calculus for Computer Scientists calculus lecture notes taught for undergrad computer science students

Math and Logic / TCS Toolkit / 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 - alternatively:
Madhur Tulsiani. Mathematical Toolkit Things prof. Madhur wish he knew in first year of grad school
Harsha & Strivastava. Toolkit for Theoretical Computer Science. Tata Institute

Math and Logic / TCS Toolkit / Lecture Notes
Gregory Valiant. The Modern Algorithmic Toolbox. Stanford It covers hashing, dimension reduction, linear and convex programming, gradient descent and regression, sampling and estimation, compressive sensing, linear-algebraic techniques (principal components analysis, singular value decomposition, spectral techniques), and an intro to differential privacy
Zhou. A Theorist's Toolkit. Illinois 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. CMU 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. Princeton 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. A Theorist's Toolkit. Princeton Aimed primarily at first and second year graduate students who plan to do research in theoretical computer science. We will introduce probabilistic, algebraic, combinatorial, and algorithmic methods useful in proofs
Kelner. Topics in Theoretical Computer Science: An Algorithmist's Toolkit. MIT It covers a collection of geometric techniques that apply broadly in modern algorithm design
Maji & Valiant. Theoretical Computer Science Toolkit. Purdue

Math and Logic / TCS Toolkit / Books
Jukna. Extremal Combinatorics Combinatorial techniques written largely with an eye to their applications in TCS, and mostly in complexity

Math and Logic / Discrete Mathematics / General
Aspnes. Notes on Discrete Mathematics Fall 2017 of the Yale course CPSC 202a, Mathematical Tools for Computer Science
Halpern. CS 2802: Discrete Structures - Honors. 2020. Cornell Honors lecture notes on discrete math -
Rosen. Handbook of Discrete and Combinatorial Mathematics A complete survey of roughly all topics of discrete math and their relevance to computing and communication engineering
Rosen. Discrete Mathematics and Its Applications A canonical discrete math textbook, accessible for even high school students
Rosenberg & Trystram. Understand Mathematics, Understand Computing: Discrete Mathematics That All Computing Students Should Know It endows the reader with an operational conceptual and methodological understanding of discrete mathematics for computing
Gries & Schneider. A Logical Approach to Discrete Math It attempts to change the way we teach logic to beginning students. Instead of teaching logic as a subject in isolation, we regard it as a basic tool and show how to use it
Introduction to Discrete Mathematics for Computer Science. UC San-Diego Learn the language of Computer Science. Learn the math that defines computer science, and practice applying it through mathematical proofs and Python code

Math and Logic / Discrete Mathematics / Probabilistic Method
Yufei. Probabilistic Methods in Combinatorics. MIT and - Showing some combinatorial object exists and prove that a certain random construction works with positive probability. The course focuses on methodology as well as combinatorial applications
Luke Postle. Probablistic Methods. Waterloo
Alon & Spencer. The Probabilistic Method A standard reference for researchers in probabilistic methods in combinatorics. Shows also connections to theoretical computer science

Math and Logic / Discrete Mathematics / Graph Theory
Graph Theory by Waterloo

Math and Logic / Discrete Mathematics / Other
Mariconda & Tonolo. Discrete Calculus: Methods for Counting An introduction to combinatorics, finite calculus, formal series, recurrences, and approximations of sums. Readers will find also deep insights into a range of less common topics rarely considered within a single book

Physics / Lecture Notes
Arora. The Computational Universe Takes us on a broad sweep of scientific knowledge and related technologies: propositional logic of the ancient Greeks (microprocessors); quantum mechanics (silicon chips); network and system phenomena (internet and search engines); computational intractability (secure encryption); and efficient algorithms (genomic sequencing)

Physics / Books
Feynman. Feynman And Computation: Exploring The Limits Of Computers
here Feynman’s Course on Computation - See also Preskill's update 40 years later

Physics / Monographs
Susskind. Three Lectures on Complexity and Black Holes Important connections between thermodynamics and complexity are proposed and discussed. Pedagogically written, serves as a fundamental introduction to black holes and their complex physical interpretation

Philosophy / Lecture Notes
6.893 Philosophy and Theoretical Computer Science. MIT It examines the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science

Philosophy / Books
Knuth. Things a Computer Scientist Rarely Talks About A general illustration of relations between faith and science
Floyd & Bokulich. Philosophical Explorations of the Legacy of Alan Turing: Turing 100 Turing’s place in the history and philosophy of science

Philosophy / Papers
Aaronson. Why Should Philosophers Care About Computational Complexity Theory It argues that computational complexity theory leads to new perspectives on the nature of mathematical knowledge and other philosophical questions
Aharonov & Vazirani, Is Quantum Mechanics Falsifiable? A Computational Perspective on the Foundations of Quantum Mechanics It describes how quantum mechanics can be tested in the limit of high complexity regime by extending the usual scientific paradigm to include
Walter Dean. Computational Complexity Theory and the Philosophy of Mathematics It highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones
Stanford Encyclopedia of Philosophy. Computational Complexity Theory The foundations of complexity theory, and its potential significance on philosophy of computer science, philosophy of mathematics and epistemology
Philip Davis. Toward a Philosophy of Computation Philosophical implication of mathematization and computerization of the world

Surveys & Monographs
Sommaruga & Strahm. Turing’s Revolution: The Impact of His Ideas about Computability A collection of historical, technical and philosophical papers
Harry Lewis. Ideas That Created the Future: Classic Papers of Computer Science Classic papers by thinkers ranging from Aristotle and Leibniz to Norbert Wiener and Gordon Moore that chart the evolution of computer science
Building Bridges I , , - Collected works in celebration of Laszlo Lovasz, Connecting discrete math with computer science
Fortnow & Homer. A Short History of Computational Complexity A historical overview of computational complexity
Goldreich. Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali It explains the remarkable work of Shafi and Silvio and their works' implications on foundations of cryptography

Community / Conferences & Workshops / Aggregators
Hermann's Conferences in TCS TCS Conferences collected in one table
CS Theory Events Aggregator An aggregator for CS theory workshops and schools
Theory Announcements DMANET spreads information on conferences, workshops, seminars etc. relating to discrete mathematics and algorithms
Salamon's List Selected Conferences

Community / Conferences & Workshops / Live
Simons' Institute Programs, Events, and workshops, that aim toward maximizing impact and engagement across the theoretical computer science community
TCS+ A series of online seminars in theoretical computer science. The goal is to make engaging talks accessible to the widest possible audience
CMU Theory Aims for a mathematical understanding of fundamental issues in Computer Science, and to use this understanding to produce better algorithms, protocols, and systems, as well as identify the inherent limitations of efficient computation

Community / Conferences & Workshops / Archived
Turing Laureates Lectures and - ACM Turing Award Laureates delivers a lecture before a forum of their choice on a subject of their choice
Computational Complexity Collection of workshops

Community / Magazines & Newsletter
EATCS Bulletin Surveys, tutorials, conferences reports, events, open problems and solutions, PhD Theses, and entertaining contributions
SIGACT News ACM's official theoretical computer science news feed
Foundations and Trends in Theoretical Computer Science It provides monographs written by leaders that give tutorial coverage of subjects, research retrospectives as well as survey papers that offer state-of-the-art reviews fall within the scope of the journal
Quanta Magazine Features breakthroughs in the field, written in an accessible style for non-experts

Community / Associations
ACM's SIGACT
European Association of TCS

Community / Blogs / Aggregators
Theory of Computing Blog Aggregator A blog Aggregator for all blogs related to TCS

Community / Blogs / Selected 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
Lipton & Regan A list of theory blogs for computer science
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
Princeton's Companion. Advice to a Young Mathematician Five contributors draw on their experiences of mathematical life and research, and to offer advice that they might have liked to receive when they were just setting-out on their careers
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
Igor Pak. How to Start a Paper Why should you introduce a conceptual preliminary motivating the story of your paper

Community / Jobs
Rubinstein & Weinberg. Research Masters in TCS A list of master programs in TCS
CS Theory Jobs TCS Jobs announcements
Yaroslavtsev. Hires spreadsheet 2022 A crowdsourced spreadsheet created to collect information about theory hires in year 2022

Community / Online Communities
TCS Stack Exchange Research-oriented Q&A of theoretical computer science
TCS Subreddit Theoretical computer science's subreddit

Other / Podcasts
Donald Knuth 1 Lex Fridman - | | | | |
Berkeley in the 80s Interviews with eminent figures in Berkeley
Simons' Theory Shorts Short accessible videos which populate theory of computation
ACM ByteCast Researchers, practitioners and innovators who are at the intersection of research and practice, sharing their experiences, lessons, visions for the future
The Legacy of Alan Turing: Pushing the Boundaries of Computation (Volume 18, Issue 3, Spring 2012). ACM, XRDS ACM's students magazine special issue for theory of computation
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
Ausiello. The Making of a New Science: A Personal Journey Through the Early Years of Theoretical Computer Science A story about people, pioneers with diverse backgrounds and characters who established a new field
Aaronson. Quantum Computing Since Democritus It covers an amazing array of topics. Beginning in antiquity with Democritus, it progresses through logic and set theory,computability and complexity theory, quantum computing, cryptography, the information content of quantum states, and the interpretation of quantum mechanics
Deutsch. The Fabric of Reality: The Science of Parallel Universes and Its Implications The Fabric of Reality presents a startlingly integrated, rational and optimistic world view – the result of taking seriously the deepest ideas of modern science and the philosophy of 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
Teuscher. Alan Turing: Life and Legacy of a Great. Springer Essays which spans the entire rich spectrum of Turing's life, research work and legacy
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
Shasha & Lazere. Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists Interviews with era's greatest scientists about their inspirations, discoveries, and personal interests

Other / Cheat Sheets
TCS Cheat Sheet A sheet of notes containing essential toolboxes needed by any theoretical computer scientist
Algorithms 20,870 5 days ago
Mathematics 8,875 5 days ago Freely available lecture notes on mathematics
nLab & - Logic, Math, Proof Assistants, and Type Theory
Cryptography 5,898 about 1 month ago
Quantum Computing 2,565 4 months ago
Math 4,482 about 1 month ago and curricula by

Backlinks from these awesome lists:

More related projects: