@harrisonqian / Awesome › wiki / computer-science / theoretical-computer-science
Public View

Theoretical Computer Science

repo: mostafatouny/awesome-theoretical-computer-science
category: Computer Science related: Algorithms · Coq

Awesome Theoretical Computer Science Awesome

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

Contents

Broad Intros<a name=broad_intros></a>

Lecture Notes<a name=broad_intros_lecture_notes></a>

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

Lecture Videos Playlists<a name=broad_intros_lecture_videos_playlists></a>

Books<a name=broad_intros_books></a>

Handbooks<a name=broad_intros_handbooks></a>

  • [Atallah & Blanton. Algorithms and Theory of Computation Handbook: General Concepts and Techniques](https://www.routledge.com/Algorithms-and-Theory-of-Computation-Handbook-Volume-1-General-Concepts/Atallah-Blanton/p/book/9781138113930) - 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](https://www.routledge.com/Algorithms-and-Theory-of-Computation-Handbook-Volume-2-Special-Topics/Atallah-Blanton/p/book/9780367384845) - A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
  • [Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity](https://mitpress.mit.edu/books/handbook-theoretical-computer-science-volume) - 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<a name=theory_of_computation></a>

Introductory<a name=theory_of_computation_introductory></a>

Lecture Notes<a name=theory_of_computation_introductory_lecture_notes></a>

MOOC<a name=theory_of_computation_introductory_mooc></a>

  • 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](https://www.udacity.com/course/computability-complexity-algorithms--ud061) - 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.

Books<a name=theory_of_computation_introductory_books></a>

Puzzles and Problem Sets<a name=theory_of_computation_introductory_puzzles_and_problem_sets></a>

Computational Complexity<a name=theory_of_computation_computational_complexity></a>

Introductory<a name=theory_of_computation_computational_complexity_introductory></a>

Lecture Videos Playlists<a name=theory_of_computation_computational_complexity_introductory_lecture_videos_playlists></a>

Lecture Notes<a name=theory_of_computation_computational_complexity_introductory_lecture_notes></a>

  • 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<a name=theory_of_computation_computational_complexity_introductory_books></a>

Big Lists<a name=theory_of_computation_computational_complexity_introductory_big_lists></a>

Communication Complexity<a name=theory_of_computation_computational_complexity_communication_complexity></a>

Lecture Notes<a name=theory_of_computation_computational_complexity_communication_complexity_lecture_notes></a>

  • 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

Books<a name=theory_of_computation_computational_complexity_communication_complexity_books></a>

Circuit Complexity<a name=theory_of_computation_computational_complexity_circuit_complexity></a>

Books<a name=theory_of_computation_computational_complexity_circuit_complexity_books></a>

Quantum Complexity<a name=theory_of_computation_computational_complexity_quantum_complexity></a>

Lecture Videos Playlists<a name=theory_of_computation_computational_complexity_quantum_complexity_lecture_videos_playlists></a>

Lecture Notes<a name=theory_of_computation_computational_complexity_quantum_complexity_lecture_notes></a>

Proof Complexity<a name=theory_of_computation_computational_complexity_proof_complexity></a>

Lecture Notes<a name=theory_of_computation_computational_complexity_proof_complexity_lecture_notes></a>

  • [Robert Robere. Proof Complexity: Algorithms and Lower Bounds](https://www.cs.mcgill.ca/~robere/comp598/index.html) - An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization.

Computability Theory<a name=theory_of_computation_computability_theory></a>

Books<a name=theory_of_computation_computability_theory_books></a>

Introductory<a name=theory_of_computation_computability_theory_books_introductory></a>

Advanced<a name=theory_of_computation_computability_theory_books_advanced></a>

Monograph<a name=theory_of_computation_computability_theory_books_monograph></a>

Logic<a name=logic></a>

Computational Complexity<a name=logic_computational_complexity></a>

Books<a name=logic_computational_complexity_books></a>

Programming Language Theory<a name=programming_language_theory></a>

Basics<a name=programming_language_theory_basics></a>

Lecture Notes<a name=programming_language_theory_basics_lecture_notes></a>

  • Cambridge Foundations of CS - It teaches programming and presents some fundamental principles of computer science, especially algorithm design.

Books<a name=programming_language_theory_basics_books></a>

Introductory<a name=programming_language_theory_introductory></a>

Books<a name=programming_language_theory_introductory_books></a>

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

Formal Verification<a name=programming_language_theory_formal_verification></a>

Lecture Notes<a name=programming_language_theory_formal_verification_lecture_notes></a>

  • UW CSE505 18au Principles of PL - Techniques for thinking crisply about programming languages, write some fascinating programs, and discuss various design tradeoffs.

Books<a name=programming_language_theory_formal_verification_books></a>

Type Theory<a name=programming_language_theory_type_theory></a>

Lecture Notes<a name=programming_language_theory_type_theory_lecture_notes></a>

Books<a name=programming_language_theory_type_theory_books></a>

Functional Programming<a name=programming_language_theory_functional_programming></a>

Lecture Notes<a name=programming_language_theory_functional_programming_lecture_notes></a>

Algorithms<a name=algorithms></a>

General<a name=algorithms_general></a>

Lecture Videos<a name=algorithms_general_lecture_videos></a>

  • [Demaine/Ku/Soloman. Introduction to Algorithms. MIT](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/) - A first course on basic algorithms and data structures. — added by Erik himself!
  • [Demaine/Devadas/Lynch. Design and Analysis of algorithms. MIT](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/) - A second course on algorithms and data structures. — added by Erik himself!
  • Erik Demaine. Advanced Data Structures. MIT - It covers major results and current directions of research in data structure.

Lecture Notes<a name=algorithms_general_lecture_notes></a>

  • 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<a name=algorithms_general_books></a>

Lower Bounds<a name=algorithms_lower_bounds></a>

Lecture Videos Playlists<a name=algorithms_lower_bounds_lecture_videos_playlists></a>

Books<a name=algorithms_lower_bounds_books></a>

Randomization & Probability<a name=algorithms_randomization__probability></a>

Lecture Notes<a name=algorithms_randomization__probability_lecture_notes></a>

  • [Mary Wootters. Randomized Algorithms and Probabilistic Analysis. Stanford](https://web.stanford.edu/class/archive/cs/cs265/cs265.1232/) - 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.
  • Harvey. First and Second Course in Randomized Algorithms. Columbia. - Respectively, undergrad and grad courses for probabilistic methods in algorithms.
  • [Lee. Randomized Algorithms and Probabilistic Analysis. Washington.](https://homes.cs.washington.edu/~jrl/teaching/cse525sp19/) - 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.

Approximation<a name=algorithms_approximation></a>

Lecture Notes<a name=algorithms_approximation_lecture_notes></a>

  • 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](https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2021/) - It includes greedy, local search, dynamic programming, randomized rounding, tree embeddings, and semidefinite programming.
  • [Gupta & Ravi. Approximation Algorithms. CMU](http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/) - It includes convex programming-based, randomness, and metric methods.

Books<a name=algorithms_approximation_books></a>

Parameterized<a name=algorithms_parameterized></a>

Lecture Videos Playlist<a name=algorithms_parameterized_lecture_videos_playlist></a>

  • [Parametarized Algorithms by Warsaw](https://www.youtube.com/playlist?list=PLzdZSKerwrXpr6hWq1s63a42YbkocAK1Q)

Books<a name=algorithms_parameterized_books></a>

  • Fedor Fomin. Parametrized Algorithms - Modern comprehensive explanation of recent tools and techniques with exercises, for graduate students.

Learning-augmented<a name=algorithms_learning-augmented></a>

Lecture Notes<a name=algorithms_learning-augmented_lecture_notes></a>

  • [Indyk & Daskalakis. Learning-augmented Algorithms. MIT](https://stellar.mit.edu/S/course/6/sp19/6.890/materials.html)

Big List<a name=algorithms_learning-augmented_big_list></a>

Information/Coding Theory<a name=informationcoding_theory></a>

Lecture Notes<a name=informationcoding_theory_lecture_notes></a>

  • 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.
  • Scott Aaronson. Quantum Information Science. Part I & Part II - 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.

Cryptography<a name=cryptography></a>

Books<a name=cryptography_books></a>

  • [Lindell. Tutorials on the Foundations of Cryptography](https://link.springer.com/book/10.1007/978-3-319-57048-8) - Advanced tutorials appropriate for self-study by experienced researchers,
  • [Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness](https://www.wisdom.weizmann.ac.il/~oded/book1.html) - 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<a name=machine_learning_theory></a>

Lecture Notes<a name=machine_learning_theory_lecture_notes></a>

  • [Blum. An Introduction to the Theory of Machine Learning. TTIC](https://home.ttic.edu/~avrim/MLT20/) - The basic theory underlying machine learning and the process of generalizing from data.
  • [Telgarsky. Deep Learning Theory. Illinois](https://mjt.cs.illinois.edu/dlt/) - 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](http://www.jennwv.com/courses/F11.html) - A broad overview of the theoretical foundations underlying common machine learning algorithms.
  • [Livni. COS 511 Theoretical Machine Learning. Princeton](https://www.cs.princeton.edu/~rlivni/cos511/cos511.html) - 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](https://people.csail.mit.edu/moitra/408b.html) - 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<a name=machine_learning_theory_books></a>

  • [Vazirani & Kearns. An Introduction to Computational Learning Theory](https://mitpress.mit.edu/books/introduction-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](https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6) - It provides an extensive theoretical account of the fundamental ideas underlying machine learning and the mathematical derivations that transform these principles into practical algorithms.

Other<a name=machine_learning_theory_other></a>

  • [Blum. Intro Machine Learning Theory](https://www.cs.cmu.edu/~avrim/Talks/mlt.pdf).
  • [Blum, et.al. Machine Learning, Game Theory, and Mechanism Design for a Networked World](https://www.cs.cmu.edu/~mblum/search/AGTML35.pdf).
  • [Agrawal & Jaiswal. When Machine Learning Meets AI and Game Theory](https://cs229.stanford.edu/proj2012/AgrawalJaiswal-WhenMachineLearningMeetsAIandGameTheory.pdf).

Game Theory<a name=game_theory></a>

Lecture Notes<a name=game_theory_lecture_notes></a>

  • [Tim Roughgarden. Complexity Theory, Game Theory, and Economics: The Barbados Lectures](https://arxiv.org/abs/1801.00734) - 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](https://chekuri.cs.illinois.edu/teaching/spring2008/agt.htm) - 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](https://feifang.info/advanced-topics-in-machine-learning-and-game-theory-fall-2021/) - A graduate-level course covering the topics at the intersection of machine learning and game theory.
  • [Xu. Topics in Learning and Game Theory](http://www.haifeng-xu.com/cs6501sp21/index.htm) - 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<a name=game_theory_books></a>

Math and Logic<a name=math_and_logic></a>

General<a name=math_and_logic_general></a>

Lecture Videos Playlist<a name=math_and_logic_general_lecture_videos_playlist></a>

Books<a name=math_and_logic_general_books></a>

Lecture Notes<a name=math_and_logic_general_lecture_notes></a>

TCS Toolkit<a name=math_and_logic_tcs_toolkit></a>

Lecture Videos Playlists<a name=math_and_logic_tcs_toolkit_lecture_videos_playlists></a>

Lecture Notes<a name=math_and_logic_tcs_toolkit_lecture_notes></a>

Books<a name=math_and_logic_tcs_toolkit_books></a>

Discrete Mathematics<a name=math_and_logic_discrete_mathematics></a>

General<a name=math_and_logic_discrete_mathematics_general></a>

Lecture Notes<a name=math_and_logic_discrete_mathematics_general_lecture_notes></a>

Books<a name=math_and_logic_discrete_mathematics_general_books></a>

MOOC<a name=math_and_logic_discrete_mathematics_general_mooc></a>

Probabilistic Method<a name=math_and_logic_discrete_mathematics_probabilistic_method></a>

Lecture Notes<a name=math_and_logic_discrete_mathematics_probabilistic_method_lecture_notes></a>

Lecture Videos Playlist<a name=math_and_logic_discrete_mathematics_probabilistic_method_lecture_videos_playlist></a>

Books<a name=math_and_logic_discrete_mathematics_probabilistic_method_books></a>

Graph Theory<a name=math_and_logic_discrete_mathematics_graph_theory></a>

Lecture Videos Playlist<a name=math_and_logic_discrete_mathematics_graph_theory_lecture_videos_playlist></a>

Other<a name=math_and_logic_discrete_mathematics_other></a>

Physics<a name=physics></a>

Lecture Notes<a name=physics_lecture_notes></a>

  • 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<a name=physics_books></a>

Monographs<a name=physics_monographs></a>

Philosophy<a name=philosophy></a>

Lecture Notes<a name=philosophy_lecture_notes></a>

Books<a name=philosophy_books></a>

Papers<a name=philosophy_papers></a>

Surveys & Monographs<a name=surveys__monographs></a>

Community<a name=community></a>

Conferences & Workshops<a name=community_conferences__workshops></a>

Aggregators<a name=community_conferences__workshops_aggregators></a>

Live<a name=community_conferences__workshops_live></a>

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

Archived<a name=community_conferences__workshops_archived></a>

Magazines & Newsletter<a name=community_magazines__newsletter></a>

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

Associations<a name=community_associations></a>

Blogs<a name=community_blogs></a>

Aggregators<a name=community_blogs_aggregators></a>

Selected Posts and Essays<a name=community_blogs_selected_posts_and_essays></a>

Jobs<a name=community_jobs></a>

Online Communities<a name=community_online_communities></a>

Other<a name=other></a>

Podcasts<a name=other_podcasts></a>

Cheat Sheets<a name=other_cheat_sheets></a>

Related Lists<a name=related_lists></a>

[[curator]]
I'm the Curator. I can help you navigate, organize, and curate this wiki. What would you like to do?