Math & CS awesome List, distinguished by proof and logic technique
This page lists names, links and short descriptions. The original list on GitHub is the source and belongs to its authors.
A modern, brief, and accessible text which introduces theoretical computer science for undergrads. It includes topics not usually included in standard undergrad text-books.
undergrad introduction to theory of computation
A series of lectures on selected notable topics in theoretical computer science.
A series of lectures on selected notable topics in theoretical computer 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.
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
A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
undergrad introduction to theory of computation
It teaches basic concepts in theoretical computer science, such as NP-completeness, and what they imply for solving tough algorithmic problems.
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.
A standard text for introducing theory of computation for undergrads.
Introductory undergrad textbook for automata, languages and theory of computation topics.
A problem-set text for automata, languages, and complexity.
(Homework) - Undergraduate course on computational complexity theory; It follows the same spirit of Sipser's part III.
It covers most of what is believed to be known to get started in complexity theory research.
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.
A golden standard textbook, Surveying computational complexity theory for graduate students and researchers.
A grad introduction to computation complexity theory, emphasizing the idea behind concepts of complexity theory.
A very gentle introduction to some fundamental ideas of computational complexity like NP-completeness and P vs NP.
An accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory.
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…
a wiki of complexity classes.
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
An excellent and very readable introductory textbook to the field of communication complexity.
A modern textbook surveying circuit complexity.
An introduction to circuit complexity, boolean functions, and computation models.
CS Masters level lectures on topics including Boson sampling, quantum interactive proofs, and quantum merlin arthur.
Focuses on cutting edge topics in quantum information that relate to Complexity of Entanglement. - see this class also
An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization.
Intuitively, It explains the idea of a computable function: a function whose values can be calculated in an effective or automatic way.
A concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results.
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.
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.
An impressive presentation of classical recursion theory. It is highly recommended to everyone interested in recursion theory.
Computer scientists, mathematicians, and philosophers discuss the conceptual foundations of the notion of computability as well as recent theoretical developments.
Presents a wide range of results in logic and computational complexity.
It teaches programming and presents some fundamental principles of computer science, especially algorithm design.
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.
Techniques for thinking crisply about programming languages, write some fascinating programs, and discuss various design tradeoffs.
A book introducing both machine-checked proof with Coq Proof Assistant and approaches to formal reasoning about program correctness.
Lean Proof Assistant.
Notes by Giovanni Sambin of a series of type theory lectures given in Padua, June 1980.
This book describes different type theories (theories of types, polymorphic and monomorphic sets, and subsets) from a computing science perspective.
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.
An online course on functional programming with Haskell programming language, and a live interactive Telegram community.
A modern course on data structures and functional programming using OCaml.
A first course on basic algorithms and data structures. — added by Erik himself!
A second course on algorithms and data structures. — added by Erik himself!
It covers major results and current directions of research in data structure.
Notably uses ideas such as randomness, approximation, high dimensional geometry. Faces uncertainty, approaches to handle big data, handling intractability, heuristic approaches, ..etc.
A legendary series by Donald Knuth on design and analysis of algorithms.
A class taking a practical approach to proving problems can't be solved efficient.
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…
It shows that games and puzzles can serve as powerful models of computation, Offering a new way of thinking about computation.
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…
Introduction to probabilistic methods in computer science.
Topics include Discrete probability, High-dimensional geometry and statistics, Information and entropy, and Markov chains and convergence to equilibrium.
Supplemental notes to the standard books by Mitzenmacher & Upfals, and Motwani & Raghavan.
A broad introduction to results and techniques with an emphasis on fundamental problems and widely applicable tools. Also more advanced and specialized topics.
It includes greedy, local search, dynamic programming, randomized rounding, tree embeddings, and semidefinite programming.
It includes convex programming-based, randomness, and metric methods.
It includes greedy, local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.
A technique-oriented approach provides a unified view. It includes detailed algorithms, proofs, analyses, examples, and applications from research papers.
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.…
Advanced tutorials appropriate for self-study by experienced researchers,
An introduction to the interwoven domains of cryptography, proofs and randomness.
The aim of the current course is to make the students familiar with some of randomized methods.
The basic theory underlying machine learning and the process of generalizing from data.
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.
A broad overview of the theoretical foundations underlying common machine learning algorithms.
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…
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…
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)?
Emphasizing issues of computational efficiency, It introduces a number of central topics in computational learning theory.
It provides an extensive theoretical account of the fundamental ideas underlying machine learning and the mathematical derivations that transform these principles into practical algorithms.
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…
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.
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…
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.
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.
A graduate-level course covering the topics at the intersection of machine learning and game theory.
A graduate level course covering topics at the interface between machine learning and game theory.
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.
Games provide mathematical models for interaction, and numerous tasks in computer science can be formulated in game-theoretic terms.
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.
A junior introduction to discrete mathematics for computer scientists. - Companion Textbook 2015
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.
A classic math-oriented introduction to computer science.
A textbook for a one quarter introductory course in theoretical computer science including logic, proof techniques, and set theory. It assumes no prerequisite other than basic programming.
for a one-semester course in theoretical computer science. It has no prerequisites other than introductory computer programming. It includes logic, sets, and function from discrete math, and automata, formal languages, and grammar from upper-level courses.
A series dedicated to math topics and their relevance to computer science.
A concise offered as an accessible reference on mathematical logic for the professional computer scientist.
It presents a careful selection of the material most needed by students in their first two years studying computer science.
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.
Suitable for undergraduate introductions to logic and early graduate courses on logic.
Semantic tableaux are used because they are theoretically sound and easy to understand.
Uses your familiarity with ideas from programming and software to teach mathematics.
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.
Presents an algorithmic approach to mathematical analysis, with a focus on modelling and on the applications of analysis.
calculus lecture notes taught for undergrad computer science students
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
Things prof. Madhur wish he knew in first year of grad school.
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.
It covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory.
It covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory.
It covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory.
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.
It covers a collection of geometric techniques that apply broadly in modern algorithm design.
Combinatorial techniques written largely with an eye to their applications in TCS, and mostly in complexity
Fall 2017 of the Yale course CPSC 202a, Mathematical Tools for Computer Science.
Honors lecture notes on discrete math - Homework
A complete survey of roughly all topics of discrete math and their relevance to computing and communication engineering.
A canonical discrete math textbook, accessible for even high school students.
It endows the reader with an operational conceptual and methodological understanding of discrete mathematics for computing
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.
Learn the language of Computer Science. Learn the math that defines computer science, and practice applying it through mathematical proofs and Python code.
and Yufei's Graph Theory book - 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.
A standard reference for researchers in probabilistic methods in combinatorics. Shows also connections to theoretical computer science.
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.
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…
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
It examines the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science.
A general illustration of relations between faith and science.
Turing’s place in the history and philosophy of science.
It argues that computational complexity theory leads to new perspectives on the nature of mathematical knowledge and other philosophical questions.
It describes how quantum mechanics can be tested in the limit of high complexity regime by extending the usual scientific paradigm to include.
It highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones.
The foundations of complexity theory, and its potential significance on philosophy of computer science, philosophy of mathematics and epistemology.
Philosophical implication of mathematization and computerization of the world.
A collection of historical, technical and philosophical papers.
Classic papers by thinkers ranging from Aristotle and Leibniz to Norbert Wiener and Gordon Moore that chart the evolution of computer science.
, Building Bridges II, Fete of Combinatorics and Computer Science - Collected works in celebration of Laszlo Lovasz, Connecting discrete math with computer science.
A historical overview of computational complexity.
It explains the remarkable work of Shafi and Silvio and their works' implications on foundations of cryptography.
TCS Conferences collected in one table.
An aggregator for CS theory workshops and schools.
DMANET spreads information on conferences, workshops, seminars etc. relating to discrete mathematics and algorithms.
Selected Conferences.
Programs, Events, and workshops, that aim toward maximizing impact and engagement across the theoretical computer science community.
A series of online seminars in theoretical computer science. The goal is to make engaging talks accessible to the widest possible audience.
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.
and Turing Laureates Interviews - ACM Turing Award Laureates delivers a lecture before a forum of their choice on a subject of their choice.
Collection of workshops.
Surveys, tutorials, conferences reports, events, open problems and solutions, PhD Theses, and entertaining contributions.
ACM's official theoretical computer science news feed.
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.
Features breakthroughs in the field, written in an accessible style for non-experts.
A blog Aggregator for all blogs related to TCS.
A research methods course, concentrating on the how rather than the what. It focuses on research practices common for computer science theory research.
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.
Manuel Blum, A very popular figure in TCS, gives research advices for juniors.
A note devoted to three rules that must be followed if you want to be successful in scientific research.
Personal Essays by Oded Goldreich. They are very unique in their conceptual message of TCS and its community.
Tips for anyone interested in theoretical computer science.
Surveys for high-school, undergraduate, and even researchers.
Posts oriented more for a less-technically matured audience.
A list of theory blogs for computer science.
Karp addresses: In 1968 computer science at Berkeley was problematic, with two departments working independently to develop programs, and his personal reflections.
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.
Lessons for students and researchers given by Steven Weinberg.
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.
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.
Why should you introduce a conceptual preliminary motivating the story of your paper.
A list of master programs in TCS.
TCS Jobs announcements.
A crowdsourced spreadsheet created to collect information about theory hires in year 2022.
Research-oriented Q&A of theoretical computer science.
Theoretical computer science's subreddit.
Interviews with eminent figures in Berkeley.
Short accessible videos which populate theory of computation.
Researchers, practitioners and innovators who are at the intersection of research and practice, sharing their experiences, lessons, visions for the future.
ACM's students magazine special issue for theory of computation.
A nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond.
A story about people, pioneers with diverse backgrounds and characters who established a new field.
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.
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.
The world of computation according to Turing, an interactive tutoring program, as told to star-crossed lovers: a novel.
Essays which spans the entire rich spectrum of Turing's life, research work and legacy.
A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine.
Interviews with era's greatest scientists about their inspirations, discoveries, and personal interests.
A sheet of notes containing essential toolboxes needed by any theoretical computer scientist.
hesreallyhim/awesome-claude-code
A hand-picked collection of the finest of resources for the most awesome of agents, Claude Code, the undisputed champion of coding companions, from the unstoppable team…
VoltAgent/awesome-agent-skills
A curated collection of 1000+ agent skills from official dev teams and the community, compatible with Claude Code, Codex, Gemini CLI, Cursor, and more.
josephmisiti/awesome-machine-learning
A curated list of awesome Machine Learning frameworks, libraries and software.
EthicalML/awesome-production-machine-learning
A curated list of awesome open source libraries to deploy, monitor, version and scale your machine learning
academic/awesome-datascience
:memo: An awesome Data Science repository to learn and apply for real world problems.
analysis-tools-dev/static-analysis
⚙️ A curated list of static analysis (SAST) tools and linters for all programming languages, config files, build tools, and more. The focus is on tools which improve…