Skip to main content

Awesome Theoretical Computer Science

The interdisciplinary of Mathematics and Computer Science; It is distinguished by its emphasis on mathemtical technique and rigour.


Contents


Broad Intros

Books

Handbooks

Theory of Computation

Introductory

Lecture Notes

Lecture Videos Playlists

MOOC

Books

Puzzles and Problem Sets

Computational Complexity

Introductory

Lecture Videos Playlists

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

Communication Complexity

Books

Circuit Complexity

Books

Quantum Complexity

Lecture Videos Playlists

Lecture Notes

Proof Complexity

Lecture Notes

Computability Theory

Books

Introductory

Advanced

Monograph

Logic

Computational Complexity

Books

Algorithms

Lecture Videos Playlists

Lecture Notes

  • 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.

Books

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.

Workshops

  • Simons Institute. Informaiton 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.

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.

Randomization

Cryptography

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)?

Books

Workshops

Conferences

Research Groups

Other

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 Lecture Videos.

Books

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.

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).

Books

Monographs

Philosophy

Lecture Notes

Books

Papers

Math/Logic Preliminaries

General

Lecture Videos Playlist

Books

Lecture Notes

TCS Inspired

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: bilibili

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.
  • Arora. A Theorist's Toolkit - 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.

Discrete Mathematics

Lecture Notes

Books

MOOC

Transition To Pure Rigour Math

  • It is already curated here - Introductory proofs and mathematical maturity.

Surveys & Monographs

Live Content

Conferences, Workshops, Events, and Talks

Aggregators

Live

  • TCS+ - A series of online seminars in theoretical computer science. The goal is to make engaging talks accessible to the widest possible audience.
  • Oxford-Warwick Complexity Meetings - Online informal talks dedicated to topics of interest in computational complexity theory and related areas. The goal is to serve as a forum for discussion and quick dissemination of results.
  • Simons' Public Lectures - Programs, Events, and workshops, that aim toward maximizing impact and engagement across the theoretical computer science community.
  • 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.

Archived

Magazines, News, and Monographs

  • 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.

Blogs Aggregators

Jobs

Aggregator

Lists

Online Communities

Other Resources

Blog Posts and Essays

Special Magazines and Workshops

Cheat Sheets

  • TCS Cheat Sheet - A sheet of notes containing essential toolboxes needed by any theoretical computer scientist.

Network Groups

  • SIGACT - Info page of ACM's Special Interest Group on Algorithms and Computation Theory.
  • PolyTCS - A project which promotes massive collaborations to solve theoretical computer science problems.
  • Complexity Network - Hosts collaboration between the three computational complexity groups at Imperial College London, University of Oxford and University of Warwick. It promotes smooth flow of ideas between the three groups and beyond.
  • List of TCS Conferences and Workshops - A list of conferences and workshops in theoretical computer science.

Related Awesome Lists

Contribute to this list: https://github.com/mostafatouny/awesome-theoretical-computer-science