Courses tagged with theory
CSE 355: Introduction to Theoretical Computer Science (3) theory
Introduces formal language theory and automata, Turing machines, decidability/undecidability, recursive function theory, and complexity theory. (ASU)
COMP 4200: Formal Languages (3) theory
Fundamentals of formal languages including mathematical models of regular sets, context-free languages and Turing machines; deterministic and non-deterministic models. (Auburn)
CSCI 3500: Theory of Computation (3) theory
A study of the major theoretical topics needed for a well-rounded knowledge of computer science. These will include automata, formal languages, asymptotic, NP-completeness, formal verification and the design of algorithms. (Augusta)
CSI 4330: Foundations of Computing (3) theory
Theoretical concepts that form the basis of computer science, including regular languages, context-free languages, Turing-decidable languages, nondeterminism, parsing, NP_Completeness, and undecidability. (Baylor)
CS 373: Automata Theory and Formal Languages (4) theory
Theory and application of automata and the languages they recognize. Regular languages, deterministic and non-deterministic finite automata, regular expressions, context-free languages, context-free grammars, pushdown automata, normal forms, context-sensitive languages, linear bounded automata, Turing recognizable languages, Turing decidable languages, Turing machines, computability, decidability, reducibility. Students will utilize an automata simulator to program finite automata, pushdown automata, and Turing machines. Application of concepts. Required activity includes student presentations. (Binghamton)
CSCI3392: Logic for Mathematicians and for Computer Scientists (3) theory
A course in mathematical logic for both mathematics and computer science majors. There will be an emphasis on applications in computer science, alongside traditional subject matter. Topics covered include propositional and predicate logic, first-order arithmetic, completeness and incompleteness theorems, computability, automated proof assistants, and satisfiability solvers. (Boston)
CS 332: Elements of the Theory of Computation (4) theory
The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church's thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems. (BU)
CS 535: Complexity Theory (4) theory
Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems. (BU)
CS 536: Quantum Computing (4) theory
Quantum physics as a powerful computational paradigm. Quantum bits (qubits), qubit operations and quantum gates, computation, and algorithms. Computational complexity classes, and efficiency of classical vs. quantum computers. Quantum Fourier transform and Shor's factorization algorithm. Physical implementation of quantum computation. (BU)
CS 537: Randomness in Computing (4) theory
Survey of probabilistic ideas of the theory of computation. Topics may include Monte Carlo and Las Vegas probabilistic computations; average case complexity and analysis; random and pseudorandom strings; games and cryptographic protocol; information; inductive inference; reliability;others. (Offered alternate years.) (BU)
CS 538: Fundamentals of Cryptography (4) theory
Basic Algorithms to guarantee confidentiality and authenticity of data. Definitions and proofs of security for practical constructions. Topics include perfectly secure encryption, pseudorandom generators, RSA and Elgamal encryption, Diffie-Hellman key agreement, RSA signatures, secret sharing, block and stream ciphers. (BU)
CS 548: Advanced Cryptography (4) theory
Continuation of CS 538. Advanced techniques to preserve confidentiality and authenticity against active attacks, zero-knowledge proofs; Fiat-Shamir signature schemes; non-malleable public-key encryption; authenticated symmetric encryption; secure multiparty protocols for tasks ranging from Byzantine agreement to mental poker to threshold cryptography. (BU)
COSI 112a: Modal, Temporal, and Spatial Logic for Language (4) theory
Examines the formal and computational properties of logical systems that are used in AI and linguistics. This includes (briefly) propositional logic and first order logic, and then an in-depth study of modal logic, temporal logic, spatial logic, and dynamic logic. Throughout the analyses of these systems, focuses on how they are used in the modeling of linguistic data. Usually offered every second year. (Brandeis)
COSI 130a: Introduction to the Theory of Computation (4) theory
Introduces topics in the theory of computation, including: finite automata and regular languages, pushdown automata and context-free languages, context-sensitive languages and Type 0 languages, Turing machines and Church's thesis, the halting problem and undecidability, and introduction to NP and PSPACE complete problems. Usually offered every year. (Brandeis)
CSCI 1010: Theory of Computation (1) theory
The course introduces basic models of computation including languages, finite-state automata and Turing machines. Proves fundamental limits on computation (incomputability, the halting problem). Provides the tools to compare the hardness of computational problems (reductions). Introduces computational complexity classes (P, NP, PSPACE and others). (Brown)
CSCI 1951-X: Formal Proof and Verification (1) theory
Proof assistants are tools that are used to check the correctness of programs. Unlike tools like model checkers and SAT solvers, proof assistants are highly interactive. Machine-checked formal proofs lead to trustworthy programs and fully specified reliable mathematics. This course introduces students to the theory and use of proof assistants, using the system Lean. We will use Lean to verify properties of functional programs and theorems from pure mathematics. We will learn the theory of deductive reasoning and the logic that these tools are based on. (Brown)
CS 21: Decidability and Tractability (9) theory
This course introduces the formal foundations of computer science, the fundamental limits of computation, and the limits of efficient computation. Topics will include automata and Turing machines, decidability and undecidability, reductions between computational problems, and the theory of NP-completeness. (Caltech)
CS 116: Reasoning about Program Correctness (36) theory
This course presents the use of logic and formal reasoning to prove the correctness of sequential and concurrent programs. (Caltech)
CS 117 abc: Computability Theory (36) theory
Various approaches to computability theory, e.g., Turing machines, recursive functions, Markov algorithms. (Caltech)
CS 118: Automata-Theoretic Software Analysis (9) theory
An introduction to the use of automata theory in the formal analysis of both concurrent and sequentially executing software systems. The course covers the use of logic model checking with linear temporal logic and interactive techniques for property-based static source code analysis. (Caltech)
CS 128: Interactive Theorem Proving (36) theory
This course introduces students to the modern practice of interactive tactic-based theorem proving using the Coq theorem prover. Topics will be drawn from logic, programming languages and the theory of computation. Topics will include: proof by induction, lists, higher-order functions, polymorphism, dependently-typed functional programming, constructive logic, the Curry-Howard correspondence, modeling imperative programs, and other topics if time permits. Students will be graded partially on attendance and will be expected to participate in proving theorems in class. (Caltech)
CS 151: Complexity Theory (39) theory
This course describes a diverse array of complexity classes that are used to classify problems according to the computational resources (such as time, space, randomness, or parallelism) required for their solution. The course examines problems whose fundamental nature is exposed by this framework, the known relationships between complexity classes, and the numerous open problems in the area. Not offered 2023-24. (Caltech)
CS 152: Introduction to Cryptography (39) theory
The course is mostly theoretical and requires mathematical maturity. There will be a small programming component. Not offered 2023-24. (Caltech)
CS 153: Current Topics in Theoretical Computer Science (12) theory
May be repeated for credit, with permission of the instructor. Students in this course will study an area of current interest in theoretical computer science. The lectures will cover relevant background material at an advanced level and present results from selected recent papers within that year's chosen theme. Students will be expected to read and present a research paper. (Caltech)
IST 4: Information and Logic (9) theory
The course explains the key concepts at the foundations of computing with physical substrates, including representations of numbers, Boolean algebra as an axiomatic system, Boolean functions and their representations, composition of functions and relations, implementing functions with circuits, circuit complexity, representation of computational processes with state diagrams, state diagrams as a composition of Boolean functions and memory, and the implementation of computational processes with finite state machines. The basic concepts covered in the course are connected to advanced topics like programming, computability, logic, complexity theory, information theory, and biochemical systems. (Caltech)
CS 254: Computability and Complexity (6) theory
An introduction to the theory of computation. What problems can and cannot be solved efficiently by computers? What problems cannot be solved by computers, period? Topics include formal models of computation, including finite-state automata, pushdown automata, and Turing machines; formal languages, including regular expressions and context-free grammars; computability and uncomputability; and computational complexity, particularly NP-completeness. (Carleton)
15-155: The Computational Lens (9) theory
What is knowable, in principle and in practice? - What does it mean to be intelligent? - Can creativity be automated? - What is the role of randomness in the universe? - How can we achieve provable guarantees of security, privacy, fairness, etc. in various settings? - What does the social network of the world look like? - Do we live in a simulation? Despite their differences, all of these questions are fundamentally about the notion of computation. And all these questions can be put under the following single umbrella: What is computation and how does it shape our understanding of life, science, technology, and society? This course is for anyone interested in these questions and more broadly, anyone interested in the algorithmic lens to tackle hard, foundational problems. Our goal will be to find reliable explanations through modeling and rigorous reasoning. We will discuss great and powerful ideas from the field of theory of computation and see how these ideas shed new light on human reasoning, laws of nature, life, technology, and society. (CMU)
15-217: Logic and Mechanized Reasoning (9) theory
Symbolic logic is fundamental to computer science, providing a foundation for the theory of programming languages, database theory, AI, knowledge representation, automated reasoning, interactive theorem proving, and formal verification. Formal methods based on logic complement statistical methods and machine learning by providing rules of inference and means of representation with precise semantics. These methods are central to hardware and software verification, and have also been used to solve open problems in mathematics. This course will introduce students to logic on three levels: theory, implementation, and application. It will focus specifically on applications to automated reasoning and interactive theorem proving. We will present the underlying mathematical theory, and students will develop the mathematical skills that are needed to design and reason about logical systems in a rigorous way. We will also show students how to represent logical objects in a functional programming language, Lean, and how to implement fundamental logical algorithms. We will show students how to use contemporary automated reasoning tools, including SAT solvers, SMT solvers, and first-order theorem provers to solve challenging problems. Finally, we will show students how to use Lean as an interactive theorem prover. (CMU)
15-251: Great Ideas in Theoretical Computer Science (12) theory
This course is about how to use theoretical ideas to formulate and solve problems in computer science. It integrates mathematical material with general problem solving techniques and computer science applications. Examples are drawn from algorithms, complexity theory, game theory, probability theory, graph theory, automata theory, algebra, cryptography, and combinatorics. Assignments involve both mathematical proofs and programming. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. (CMU)
15-453: Formal Languages, Automata, and Computability (9) theory
An introduction to the fundamental ideas and models underlying computing: finite automata, regular sets, pushdown automata, context-free grammars, Turing machines, undecidability, and complexity theory. (CMU)
15-455: Undergraduate Complexity Theory (9) theory
Complexity theory is the study of how much of a resource (such as time, space, parallelism, or randomness) is required to perform some of the computations that interest us the most. In a standard algorithms course, one concentrates on giving resource efficient methods to solve interesting problems. In this course, we concentrate on techniques that prove or suggest that there are no efficient methods to solve many important problems. We will develop the theory of various complexity classes, such as P, NP, co-NP, PH, #P, PSPACE, NC, AC, L, NL, UP, RP, BPP, IP, and PCP. We will study techniques to classify problems according to our available taxonomy. By developing a subtle pattern of reductions between classes we will suggest an (as yet unproven!) picture of how by using limited amounts of various resources, we limit our computational power. (CMU)
CSDS 343: Theoretical Computer Science (3) theory
Introduction to different classes of automata and their correspondence to different classes of formal languages and grammars, computability, complexity and various proof techniques. (Case)
CP405: Theory of Computation (1) theory
Examination of the logical basis of computation. Topics include automata theory, Turing machines, time complexity, and space complexity theory. (Colorado)
COMS W3261: Computer Science Theory (3) theory
Regular languages: deterministic and non-deterministic finite automata, regular expressions. Context-free languages: context-free grammars, push-down automata. Turing machines, the Chomsky hierarchy, and the Church-Turing thesis. Introduction to Complexity Theory and NP-Completeness (Columbia)
COMS W4236: Intro-Computational Complexity (3) theory
Develops a quantitative theory of the computational difficulty of problems in terms of the resources (e.g. time, space) needed to solve them. Classification of problems into complexity classes, reductions, and completeness. Power and limitations of different modes of computation such as nondeterminism, randomization, interaction, and parallelism (Columbia)
COMS W4261: Intro to Cryptography (3) theory
An introduction to modern cryptography, focusing on the complexity-theoretic foundations of secure computation and communication in adversarial environments; a rigorous approach, based on precise definitions and provably secure protocols. Topics include private and public key encryption schemes, digital signatures, authentication, pseudorandom generators and functions, one-way functions, trapdoor functions, number theory and computational hardness, identification and zero knowledge protocols (Columbia)
COMS W4281: Intro to Quantum Computing (3) theory
Introduction to quantum computing. Shor's factoring algorithm, Grover's database search algorithm, the quantum summation algorithm. Relationship between classical and quantum computing. Potential power of quantum computers (Columbia)
CS 4810: Introduction to Theory of Computing (3) theory
Introduction to the modern theory of computing: automata theory, formal languages, and effective computability. (Cornell)
CS 4814: Introduction to Computational Complexity (3) theory
Explores the power and limitations of efficient computation. Understanding how the notion of efficient computation changes with respect to resources such as time, space, randomness, advice, and interaction. Concrete computational models that we will study will include Turing machines, Boolean circuits, Decision trees, and Branching Programs. Advanced topics may include error-correcting codes, probabilistic checkable proofs, and circuit lower bounds. (Cornell)
CS 4830: Introduction to Cryptography (3) theory
A rigorous introduction to the theoretical foundations of the cryptography that powers much of the modern world. Topics include one-way functions, secret-key encryption, zero-knowledge proofs, signatures, public-key encryption etc. As this is a theoretical class, the emphasis will be on formal definitions and proofs. (Cornell)
COSC 39: Theory of Computation (1) theory
This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, pushdown automata, Turing machines, computability, and NP-completeness. (Dartmouth)
COSC 40: Computational Complexity (1) theory
This course covers the basics of computational complexity, whose broad goal is to classify computational problems into classes based on their inherent resource requirements. Five key computational resources are studied: time, space, nondeterminism, randomness, and interaction. Key concepts studied include reductions, the polynomial hierarchy, Boolean circuits, pseudorandomness and one-way functions, probabilistic proof systems, and hardness of approximation. (Dartmouth)
CPS 337: Theoretical Foundations of Computer Science (1) theory
An introduction to the theoretical models used to understand the capabilities and fundamental limitations of computational devices. Topics include formal languages, automata, grammars, computability, reductions, and complexity. (F&M)
CS 4510: Automata and Complexity Theory (3) theory
Computational machine models and their language classes. Undecidability. Resource-bounded computations. Central complexity-theoretic concepts such as complexity classes, reducibility and completeness. (Georgia Tech)
CS 6520: Computational Complexity Theory (3) theory
Introduction to resource-bounded computations, central complexity-theoretic concepts such as complexity classes, reducibility, completeness, and intractability. (Georgia Tech)
COMPSCI 37: Incentives in the Wild: from Tanking in Sports to Mining Cryptocurrencies (4) theory
How could it be that paving a new road might increase congestion for all drivers? Why would a professional sports team ever try not to score in a game that it wants to win? Why would any student rank high schools not in their order of preference when applying? And what are some incentive pitfalls that the designer of a cryptocurrency system should be aware of? In this course, we will examine seemingly strange social phenomena, use mathematical tools to model them and to analyze how and why distorted incentives give rise to them, and explore potential mechanisms to eliminate such phenomena. (Harvard)
COMPSCI 229R: Topics in Theoretical Computer Science: Essential Coding Theory (4) theory
Introduces essential elements the theory of error-correcting codes. Focuses on the basic results in the area, taught from first principles. Special focus will be given on results of asymptotic or algorithmic significance. Principal topics include: 1. Construction and existence results for error-correcting codes 2. Limitations on the combinatorial performance of error-correcting codes 3. Decoding algorithms 4. Applications to other areas of mathematics and computer science. Lecture notes for this course from previous offerings give further details on the material covered. These may be found at http://madhu.seas.harvard.edu/courses/Spring2020 Notes: Instructor permission needed to enroll. Students interested in the course should write to the instructor explaining what their background is in CS and Math, and explaining why they are interested in the course. Note that the course is an advanced grad course and students are expected to have a strong math background in addition to the CS courses listed in Recommended Prep. (Harvard)
COMPSCI 1200: Introduction to Algorithms and their Limitations (4) theory
An introductory course in theoretical computer science, aimed at giving students the power of using mathematical abstraction and rigorous proof to understand computation. Thus equipped, students will be able to design and use algorithms that apply to a wide variety of computational problems, with confidence about their correctness and efficiency, as well as recognize when a problem may have no algorithmic solution. At the same time, they will gain an appreciation for the beautiful mathematical theory of computation that is independent of (indeed, predates) the technology on which it is implemented. (Harvard)
COMPSCI 1210: Introduction to Theoretical Computer Science (4) theory
Computation occurs over a variety of substrates including silicon, neurons, DNA, the stock market, bee colonies and many others. In this course we will study the fundamental capabilities and limitations of computation, including the phenomenon of universality and the duality of code and data. Some of the questions we will touch upon include: Are there functions that cannot be computed? Are there true mathematical statements that can't be proven? Are there encryption schemes that can't be broken? Is randomness ever useful for computing? Can we use the quirks of quantum mechanics to speed up computation? (Harvard)
COMPSCI 1260: Fairness and Privacy: Perspectives from Law and Probability (4) theory
Algorithms are mathematical objects with real life consequences. How do you say “fairness” and “privacy” in mathematics? How do existing theoretical computer science formulations mesh with legal privacy and nondiscrimination notions? Drawing on key concepts from differential privacy, the theory of algorithmic fairness, and crytography, the course focuses on the analysis and mitigation of privacy loss and unfairness in machine learning and data analysis. Through joint readings and weekly class meetings with the HLS course of the same name, students will develop disciplinary “bilingualism.” (Harvard)
COMPSCI 1270: Cryptography (4) theory
Cryptography is as old as human communication itself, but has undergone a revolution in the last few decades. It is now about much more than "secret writing" and includes seemingly paradoxical notions such as communicating securely without a shared secret, and computing on encrypted data. In this challenging but rewarding course we will start from the basics of private and public key cryptography and go all the way up to advanced notions such as fully homomorphic encryption and software obfuscation. This is a proof-based course that will be best appreciated by mathematically mature students. (Harvard)
COMPSCI 1360: Economics and Computation (4) theory
The course examines the interplay between economic thinking and computational thinking as it relates to the design of online platforms and societal decision-making mechanisms. The focus is on fundamental concepts, modeling, and mathematical analysis. Topics covered include game theory, incentive alignment, matching, social choice, fair division and social networks. Special attention is given to ideas that draw on both disciplines, such as worst-case bounds on the inefficiency of equilibria, voting rules that are computationally hard to manipulate, and approximation algorithms that discourage strategic behavior. (Harvard)
COMPSCI 2210: Computational Complexity (4) theory
A quantitative theory of the resources needed for computing and the impediments to efficient computation. The models of computation considered include ones that are finite or infinite, deterministic, randomized, quantum or nondeterministic, discrete or algebraic, sequential or parallel. (Harvard)
COMPSCI 2231: Quantum Computation and Quantum Complexity (4) theory
An introduction to the quantum view on a variety of disciplines: algorithms, complexity, cryptography and information. Course will elucidate the source of quantum advantage in computation, ties of quantum computation with physics, and the power of entanglement. (Harvard)
COMPSCI 2260: Topics in Theory for Society: Differential Privacy (4) theory
Differential Privacy is a mathematically rigorous definition of privacy that has become the de facto standard for statistical analysis of large datasets. Differential privacy provides a concrete measure of privacy loss, and differentially private algorithms are equipped with a parameter for controlling this loss. A signal property of differential privacy is closure under composition, meaning that we can understand and control the cumulative privacy loss as the data are subjected to multiple analyses. In consequence, differential privacy is 'programmable:' one can combine simple differentially private computational primitives in creative ways to obtain privacy-preserving algorithms for complex analytical tasks. The course will cover (1) the basics of differential privacy: the definition and its properties, computational primitives, and composition theorems; (2) selected advanced differentially private algorithms drawn from the literature and a wide range of application areas from industry to the US Census; and (3) lower bounds: limits on what differential privacy – or any privacy technology – can offer. (Harvard)
COMPSCI 2280: Computational Learning Theory (4) theory
Possibilities of and limitations to performing learning by a computational process. Computationally feasible generalization and its limits. Topics include computational models of learning, polynomial time learnability, learning from examples and from queries to oracles. Applications to Boolean functions, languages and geometric functions. Darwinian evolution as learning. (Harvard)
COMPSCI 2370: Economic Analysis as a Frontier of Theoretical Computer Science (4) theory
How can we use tools from statistical learning theory to design better auctions? Can we use cryptography to better implement matching mechanisms? And how should we approach formally proving that welfare in Nash equilibria for many games is not 'much worse' than in the social optimum? This course explores the application of diverse ideas, techniques, and solution aesthetics from theoretical computer science to derive meaningful new insights into classic economic problems. The three main themes are approximation theorems (including bounding the loss in revenue or welfare due to lack of information, to strategic behavior, or to impracticality of the optimal mechanism); various notions of complexity (including computational complexity, communication complexity, and sample complexity); and cryptographic tools (including cryptographic commitments, multiparty computation, and zero-knowledge proofs). Economic applications mostly include analysis of equilibria, pricing, and mechanism design. (Harvard)
COMPSCI 2380: Optimized Democracy (4) theory
The course examines the mathematical and algorithmic foundations of democracy, running the gamut from theory to applications. The goal is to provide students with a rigorous perspective on, and a technical toolbox for, the design of better democratic systems. Topics include computational social choice (identifying optimal voting rules), fairness in political redistricting (avoiding gerrymandering) and apportionment (allocating seats on a representative body), sortition (randomly selecting citizens assemblies), liquid democracy (transitively delegating votes), and weighted voting games (analyzing legislative power through cooperative game theory). (Harvard)
COMPSCI 2540: Formal Methods for Computer Security (4) theory
This course explores formal methods for computer security, including formal security models, relationships between security properties/policies and enforcement mechanisms, principled techniques and tools to specify, analyze, and construct secure computer systems. Specific topics include properties, hyperproperties, side channels, reasoning about cryptographic protocols, information flow, authorization logics, and verification techniques. Assessment will include homeworks and/or small projects during the semester as well as a final, larger project that is open-ended and driven by student interests. (Harvard)
MIT 6.5410: Advanced Complexity Theory (4) theory
Current research topics in computational complexity theory. Nondeterministic, alternating, probabilistic, and parallel computation models. Boolean circuits. Complexity classes and complete sets. The polynomial-time hierarchy. Interactive proof systems. Relativization. Definitions of randomness. Pseudo-randomness and derandomizations. Interactive proof systems and probabilistically checkable proofs. (Harvard)
6.1400: Computability and Complexity Theory (12) theory
Mathematical introduction to the theory of computing. Rigorously explores what kinds of tasks can be efficiently solved with computers by way of finite automata, circuits, Turing machines, and communication complexity, introducing students to some major open problems in mathematics. Builds skills in classifying computational tasks in terms of their difficulty. Discusses other fundamental issues in computing, including the Halting Problem, the Church-Turing Thesis, the P versus NP problem, and the power of randomness. (MIT)
6.1420: Fixed Parameter and Fine-grained Computation (12) theory
An overview of the theory of parameterized algorithms and the 'problem-centric' theory of fine-grained complexity, both of which reconsider how to measure the difficulty and feasibility of solving computational problems. Topics include: fixed-parameter tractability (FPT) and its characterizations, the W-hierarchy (W[1], W[2], W[P], etc.), 3-sum-hardness, all-pairs shortest paths (APSP)-equivalences, strong exponential time hypothesis (SETH) hardness of problems, and the connections to circuit complexity and other aspects of computing. (MIT)
6.5400: Theory of Computation (12) theory
A more extensive and theoretical treatment of the material in 6.1400/18.400, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. (MIT)
6.5410: Advanced Complexity Theory (12) theory
Current research topics in computational complexity theory. Nondeterministic, alternating, probabilistic, and parallel computation models. Boolean circuits. Complexity classes and complete sets. The polynomial-time hierarchy. Interactive proof systems. Relativization. Definitions of randomness. Pseudo-randomness and derandomizations. Interactive proof systems and probabilistically checkable proofs. (MIT)
6.5420: Randomness and Computation (12) theory
The power and sources of randomness in computation. Connections and applications to computational complexity, computational learning theory, cryptography and combinatorics. Topics include: probabilistic proofs, uniform generation and approximate counting, Fourier analysis of Boolean functions, computational learning theory, expander graphs, pseudorandom generators, derandomization. (MIT)
6.5430: Quantum Complexity Theory (12) theory
Introduction to quantum computational complexity theory, the study of the fundamental capabilities and limitations of quantum computers. Topics include complexity classes, lower bounds, communication complexity, proofs and advice, and interactive proof systems in the quantum world; classical simulation of quantum circuits. The objective is to bring students to the research frontier. (MIT)
CS 2800: Logic and Computation (4) theory
Introduces formal logic and its connections to computer and information science. Offers an opportunity to learn to translate statements about the behavior of computer programs into logical claims and to gain the ability to prove such assertions both by hand and using automated tools. Considers approaches to proving termination, correctness, and safety for programs. Discusses notations used in logic, propositional and first order logic, logical inference, mathematical induction, and structural induction. Introduces the use of logic for modeling the range of artifacts and phenomena that arise in computer and information science. (Northeastern)
CS 3800: Theory of Computation (4) theory
Introduces the theory behind computers and computing aimed at answering the question, “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, nondeterminism, nonregular languages, context-free languages, pushdown automata, and noncontext-free languages. The computability portion includes Turing machines, the Church-Turing thesis, decidable languages, and the Halting theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P vs. NP question, and NP-completeness. (Northeastern)
CS 4805: Fundamentals of Complexity Theory (4) theory
Reviews basic material such as automata, Turing machines, (un)decidability, time complexity, P vs. NP, and NP-completeness. Studies core topics in computational complexity, including time and space complexity, polynomial hierarchy, circuit complexity, probabilistic computation, interactive proofs, and hardness of approximation. Optional topics may include Gödel's incompleteness theorem, Kolgomorov complexity, cryptography, quantum computing, communication complexity, lower bounds, or pseudorandomness. (Northeastern)
CS 4820: Computer-Aided Reasoning (4) theory
Covers fundamental concepts, techniques, and algorithms in computer-aided reasoning, including propositional logic, variants of the DPLL algorithm for satisfiability checking, first-order logic, unification, tableaux, resolution, Horn clauses, congruence closure, rewriting, Knuth-Bendix completion, decision procedures, Satisfiability Modulo Theories, recursion, induction, termination, Presburger arithmetic, quantifier elimination, and interactive theorem proving. Offers students an opportunity to develop and implement a reasoning engine in a sequence of projects over the course of the semester. Also covers how to formalize and reason about computational systems using a modern interactive theorem prover. (Northeastern)
CS 4830: System Specification, Verification, and Synthesis (4) theory
Covers the fundamental topics in formal modeling and specification (transition systems, temporal logic, regular and omega-regular languages, safety and liveness properties, etc.); computer-aided verification (state-space exploration, model checking, bounded-model checking, binary-decision diagrams, symbolic model checking, etc.); compositionality and assume-guarantee reasoning; contracts; and component-based design. Also covers fundamental topics in computer-aided synthesis of correct-by-construction systems, starting from high-level formal specifications or from example scenarios. Designing large and complex systems (digital circuits, embedded control systems such as automated vehicles, computerized healthcare devices such as pacemakers, cyber-physical systems such as automated intersections, etc.) and their software cannot be done by hand. Instead, designers use computer-aided techniques that allow them to build system models and verify correctness of the design before the real system is actually built. (Northeastern)
COMP_SCI 335-0: Introduction to the Theory of Computation (1) theory
Mathematical foundations of computation, including computability, relationships of time and space, and the P vs. NP problem. (Northwestern)
CSCI 101: Introduction to Languages and the Theory of Computation (1) theory
This class investigates models of computation such as finite-state automata and Turing machines, formal languages such as context free grammars, and computability. Connections to applications such as lexical analysis and parsing will be explored. Students will learn to read and to construct formal proofs in this context. (Pomona)
COS 487: Theory of Computation (1) theory
Studies the limits of computation by identifying tasks that are either inherently impossible to compute, or impossible to compute within the resources available. Introduces students to computability and decidability, Godel's incompleteness theorem, computational complexity, NP-completeness, and other notions of intractability. This course also surveys the status of the P versus NP question. Additional topics may include: interactive proofs, hardness of computing approximate solutions, cryptography, and quantum computation. (Princeton)
CS 48300: Introduction To The Theory Of Computation (3) theory
Turing machines and the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; decidability of logical theories; Kolmogorov complexity; time classes; P, NP, NP-complete; space classes; Savitch’s theorem, PSPACE-completeness, NL-completeness; hierarchy theorems; approximation theorems; probabilistic algorithms; applications of complexity to parallel computation and cryptography. Typically offered Fall Spring. (Purdue)
CS 56000: Reasoning About Programs (3) theory
The course focuses on the logical foundations and algorithmic techniques used to ensure program correctness. With an emphasis on automated program verification and synthesis, the course covers classical concepts and techniques such as Hoare logic, abstract interpretation, abstraction-refinement and bounded model checking. The course also exposes students to approaches for program synthesis, a new frontier for program reasoning, such as inductive synthesis, synthesis using version space algebras, constraint-based synthesis and synthesis based on machine-learning techniques. The courses emphasizes both theoretical foundations as well as hands-on experience with verification/synthesis tools and SAT/SMT solvers. Students are expected to have completed undergraduate coursework in Foundations of Computer Science (CS 18200) or equivalent, Systems Programming (CS 25200) or equivalent, and Introduction to the Analysis of Algorithms (CS 38100) or equivalent. Mathematical maturity is expected. Typically offered Fall. (Purdue)
COMP 481: Automata, Formal Languages, and Computability (3) theory
Finite automata, regular expressions, regular languages, pushdown automata, context-free languages, Turing machines, recursive languages, computability, and solvability. It is strongly recommended that students complete three semesters of Mathematics before enrolling in this course. (Rice)
COMP 487: Computational Complexity (3) theory
In Computational Complexity we study the computational resources (time, space, communication, etc.) that are required to solve computational problems via various computational needs. Specifically, we are interested in classifying computational problems with classes of other problems that require similar amount of resources to solve. (Rice)
CSSE 474: Theory of Computation (4) theory
Students study mathematical models by which to answer three questions: What is a computer? What limits exist on what problems computers can solve? What does it mean for a problem to be hard? Topics include models of computation (including Turing machines), undecidability (including the Halting Problem) and computational complexity (including NP-completeness). (Rose-Hulman)
CS 103: Mathematical Foundations of Computing (35) theory
What are the theoretical limits of computing power? What problems can be solved with computers? Which ones cannot? And how can we reason about the answers to these questions with mathematical certainty? This course explores the answers to these questions and serves as an introduction to discrete mathematics, computability theory, and complexity theory. At the completion of the course, students will feel comfortable writing mathematical proofs, reasoning about discrete structures, reading and writing statements in first-order logic, and working with mathematical models of computing devices. Throughout the course, students will gain exposure to some of the most exciting mathematical and philosophical ideas of the late nineteenth and twentieth centuries. Specific topics covered include formal mathematical proofwriting, propositional and first-order logic, set theory, binary relations, functions (injections, surjections, and bijections), cardinality, basic graph theory, the pigeonhole principle, mathematical induction, finite automata, regular expressions, the Myhill-Nerode theorem, context-free grammars, Turing machines, decidable and recognizable languages, self-reference and undecidability, verifiers, and the P versus NP question. Students with significant proofwriting experience are encouraged to instead take CS 154. Students interested in extra practice and support with the course are encouraged to concurrently enroll in CS 103A. (Stanford)
CS 103ACE: Mathematical Problem-solving Strategies (1) theory
Problem solving strategies and techniques in discrete mathematics and computer science. Additional problem solving practice for CS 103. In-class participation required. (Stanford)
CS 154: Introduction to the Theory of Computation (34) theory
This course provides a mathematical introduction to the following questions: What is computation? Given a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in computer science and mathematics. By the end of this course, students will be able to classify computational problems in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.). Students will gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem. (Stanford)
CS 157: Computational Logic (3) theory
Rigorous introduction to Symbolic Logic from a computational perspective. Encoding information in the form of logical sentences. Reasoning with information in this form. Overview of logic technology and its applications - in mathematics, science, engineering, business, law, and so forth. Topics include the syntax and semantics of Propositional Logic, Relational Logic, and Herbrand Logic, validity, contingency, unsatisfiability, logical equivalence, entailment, consistency, natural deduction (Fitch), mathematical induction, resolution, compactness, soundness, completeness. (Stanford)
CS 163: The Practice of Theory Research (3) theory
(Previously numbered CS 353). Introduction to research in the Theory of Computing, with an emphasis on research methods (the practice of research), rather than on any particular body of knowledge. The students will participate in a highly structured research project: starting from reading research papers from a critical point of view and conducting bibliography searches, through suggesting new research directions, identifying relevant technical areas, and finally producing and communicating new insights. The course will accompany the projects with basic insights on the main ingredients of research. Research experience is not required, but basic theory knowledge and mathematical maturity are expected. The target participants are advanced undergrads as well as MS students with interest in CS theory. (Stanford)
CS 254: Computational Complexity (3) theory
An introduction to computational complexity theory. Topics include the P versus NP problem and other major challenges of complexity theory; Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem; P, NP, coNP, and the polynomial hierarchy; The power of randomness in computation; Non-uniform computation and circuit complexity; Interactive proofs. (Stanford)
CS 254B: Computational Complexity II (3) theory
A continuation of CS 254 (Computational Complexity). Topics include Barriers to P versus NP; The relationship between time and space, and time-space tradeoffs for SAT; The hardness versus randomness paradigm; Average-case complexity; Fine-grained complexity; Current and new areas of complexity theory research. (Stanford)
CS 259Q: Quantum Computing (3) theory
This course introduces the basics of quantum computing. Topics include: qubits, entanglement, and non-local correlations; quantum gates, circuits, and compilation algorithms; basic quantum algorithms such as Simon's algorithm and Grover's algorithm; Shor's factoring algorithm and the hidden subgroup problem; Hamiltonian simulation; stabilizer circuits, the Gottesman-Knill theorem, and the basics of quantum error correction. (Stanford)
CS 353: Seminar on Logic & Formal Philosophy (24) theory
Contemporary work. May be repeated a total of three times for credit. (Stanford)
CS 354: Topics in Intractability: Unfulfilled Algorithmic Fantasies (3) theory
Over the past 45 years, understanding NP-hardness has been an amazingly useful tool for algorithm designers. This course will expose students to additional ways to reason about obstacles for designing efficient algorithms. Topics will include unconditional lower bounds (query- and communication-complexity), total problems, Unique Games, average-case complexity, and fine-grained complexity. (Stanford)
CS 359A: Research Seminar in Complexity Theory (3) theory
A research seminar on computational complexity theory. The focus of this year's offering will be on concrete complexity, a major strand of research in modern complexity theory. We will cover fundamental techniques and major results concerning basic models of computation such as circuits, decision trees, branching problems, and halfspaces. (Stanford)
CS 359D: Quantum Complexity Theory (3) theory
Introduction to quantum complexity theory. Topics include: the class BQP and its relation to other complexity classes; quantum query and communication complexity; quantum proof systems, Hamiltonian complexity, and the quantum PCP conjecture; the complexity & verification of quantum sampling experiments; and quantum cryptography. (Stanford)
CS 360: Simplicity and Complexity in Economic Theory (35) theory
Technology has enabled the emergence of economic systems of formerly inconceivable complexity. Nevertheless, some technology-related economic problems are so complex that either supercomputers cannot solve them in a reasonable time, or they are too complex for humans to comprehend. Thus, modern economic designs must still be simple enough for humans to understand, and must address computationally complex problems in an efficient fashion. This topics course explores simplicity and complexity in economics, primarily via theoretical models. We will focus on recent advances. Key topics include (but are not limited to) resource allocation in complex environments, communication complexity and information aggregation in markets, robust mechanisms, dynamic matching theory, influence maximization in networks, and the design of simple (user-friendly) mechanisms. Some applications include paired kidney exchange, auctions for electricity and for radio spectrum, ride-sharing platforms, and the diffusion of information. (Stanford)
CPSC 046: Theory of Computation (1) theory
This study of various models of computation leads to a characterization of the kinds of problems that can and cannot be solved by a computer. Solvable problems will be classified with respect to their degree of difficulty. Topics to be covered include formal languages and finite state devices; Turing machines; and other models of computation, computability, and complexity. (Swarthmore)
CSCE 222: Discrete Structures for Computing (3) theory
Mathematical foundations from discrete mathematics for analyzing computer algorithms, for both correctness and performance; introduction to models of computation, including finite state machines and Turing machines. (Texas A&M)
CSCE 433: Formal Languages and Automata (3) theory
Basic types of abstract languages and their acceptors; the Chomsky hierarchy; solvability and recursive function theory; application of theoretical results to practical problems. (Texas A&M)
CS 170: Computation Theory (4) theory
Models of computation: Turing machines, pushdown automata, and finite automata. Grammars and formal languages including context-free languages and regular sets. Important problems including the halting problem and language equivalence theorems. (Tufts)
CY385: Cyber Algorithmic Foundations (3) theory
This course grounds cadets in algorithms and key topics in the theory of computation, with a focus on how key theoretical techniques help the cyber professional discern what is and is not feasible in cyberspace. Topics include analysis of algorithms, how to use algorithmic complexities to choose between algorithms, algorithmic approaches, and an introduction to formal languages, automata, computational theory, decidability, and the Chomsky hierarchy. (West Point)
CS474: Intro to Theoretical Comp Sci (3) theory
This course introduces computer science theory through the study of abstract machines, grammars, languages, decidability, and NP-completeness. Students evaluate fundamental limits of these machines and grammars and classify languages according to the Chomsky hierarchy; apply various techniques to prove facts about these machines, grammars, and languages; recognize the difference between problems that are and are not solvable; and determine when a problem is NP-complete. Throughout, the course links fundamental computer science theory to modern-day practical computing devices and computational problems. (West Point)
CS 172: Computability and Complexity (4) theory
Finite automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness. (Berkeley)
CSE 105: Theory of Computability (4) theory
An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expressions. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability. (UCSD)
CMPSC 40: Foundations of Computer Science (5) theory
Introduction to the theoretical underpinnings of computer science. Topics include propositional predicate logic, set theory, functions and relations, counting, mathematical induction and recursion (generating functions). (UCSB)
CMPSC 138: Automata and Formal Languages (4) theory
Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to Turing machines and computability. (UCSB)
CS 474: Logic in Computer Science (3) theory
An introduction to mathematical logic from the perspective of computer science, emphasizing both computable aspects of logic, especially automated reasoning, as well as applications of logic to computer science in artificial intelligence, databases, formal methods, and theoretical computer science. (Illinois)
CS 475: Formal Models of Computation (3) theory
Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; linear-bounded automata and context-sensitive languages; computability and the halting problem; undecidable problems; recursive functions; Chomsky hierarchy; computational complexity. (Illinois)
CS 420: Automata Theory (4) theory
Provides a mathematical basis for computability and complexity. Models of computation, formal languages, Turing machines, solvability. Nondeterminism and complexity classes. (UO)
CIS 2620: Automata, Computability, and Complexity (1) theory
This course explores questions fundamental to computer science such as which problems cannot be solved by computers, can we formalize computing as a mathematical concept without relying upon the specifics of programming languages and computing platforms, and which problems can be solved efficiently. The topics include finite automata and regular languages, context-free grammars and pushdown automata, Turing machines and undecidability, tractability and NP-completeness. The course emphasizes rigorous mathematical reasoning as well as connections to practical computing problems such as test processing, parsing, XML query languages, and program verification. (Penn)
CIS 5110: Theory of Computation (1) theory
Review of regular and context-free languages and machine models. Turing machines and RAM models, Decidability, Halting problem, Reductions, Recursively enumerable sets, Universal TMs, Church/Turing thesis. Time and space complexity, hierarchy theorems, the complexity classes P, NP, PSPACE, L, NL, and co-NL. Reductions revisited, Cook-Levin Theorem, completeness, NL = co-NL. Advanced topics as time permits: Circuit complexity and parallel computation, randomized complexity, approximability, interaction and cryptography. (Penn)
CIS 5180: Topics in Logic: Finite Model Theory and Descriptive Complexity (1) theory
This course will examine the expressive power of various logical languages over the class of finite structures. The course begins with an exposition of some of the fundamental theorems about the behavior of first-order logic in the context of finite structures, in particular, the Ehrenfeucht-Fraisse Theorem and the Trahktenbrot Theorem. The first of these results is used to show limitations on the expressive power of first-order logic over finite structures while the second result demonstrates that the problem of reasoning about finite structures using first-order logic is surprisingly complex. The course then proceeds to consider various extensions of first-order logic including fixed-point operators, generalized quantifiers, infinitary languages, and higher-order languages. The expressive power of these extensions will be studied in detail and will be connected to various problems in the theory of computational complexity. This last motif, namely the relation between descriptive and computational complexity, will be one of the main themes of the course. (Penn)
CMPU 240: Theory of Computation (1) theory
Introduces the theory of computation while exploring the fundamental powers and limitations of all computing machines. Considers appropriate models of a computer and what problems are and are not solvable in such models. Aims to develop an understanding of the intimate connection between computation and language recognition, using as examples several classes of abstract machines and the corresponding classes of formal languages. Students learn how to reason about the nature of computation itself, and develop the intuition of a computer scientist. Provides theoretical foundations for CMPU 331 and 366. (Vassar)
CSE 447T: Introduction to Formal Languages and Automata (3) theory
An introduction to the theory of computation, with emphasis on the relationship between formal models of computation and the computational problems solvable by those models. Specifically, this course covers finite automata and regular languages; Turing machines and computability; and basic measures of computational complexity and the corresponding complexity classes. (Washington U.)
CS 235: Theory of Computation (1) theory
This course offers an introduction to the theory of computation. Topics include languages, regular expressions, finite automata, grammars, pushdown automata, and Turing machines. The first part of the course covers the Chomsky hierarchy of languages and their associated computational models. The second part of the course focuses on decidability issues and unsolvable problems. The final part of the course investigates complexity theory. (Wellesley)
COMP 301: Automata Theory and Formal Languages (1) theory
This course is an introduction to formalisms studied in computer science and mathematical models of computing machines. The language formalisms discussed include regular, context-free, and recursively enumerable languages. The machines discussed include finite-state automata, pushdown automata and Turing machines. (Wesleyan)
CSCI 357: Algorithmic Game Theory (1) theory
This course focuses on topics in game theory and mechanism design from a computational perspective. We will explore questions such as: how to design algorithms that incentivize truthful behavior, that is, where the participants have no incentive to cheat? Should we let drivers selfishly minimize their commute time or let a central algorithm direct traffic? Does Arrow's impossibility result mean that all voting protocols are doomed? The overarching goal of these questions is to understand and analyze selfish behavior and whether it can or should influence system design. Students will learn how to model and reason about incentives in computational systems both theoretically and empirically. Topics include types of equilibria, efficiency of equilibria, auction design and mechanism design with money, two-sided markets and mechanism design without money, incentives in computational applications such as P2P systems, and computational social choice. (Williams)
CSCI 361: Theory of Computation (1) theory
This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free grammars, and Turing machines. These models provide a mathematical basis for the study of computability theory--the examination of what problems can be solved and what problems cannot be solved--and the study of complexity theory--the examination of how efficiently problems can be solved. Topics include the halting problem and the P versus NP problem. (Williams)
CPSC 455: Economics and Computation (1) theory
A mathematically rigorous investigation of the interplay of economic theory and computer science, with an emphasis on the relationship of incentive-compatibility and algorithmic efficiency. (Yale)
CPSC 468: Computational Complexity (1) theory
Introduction to the theory of computational complexity. (Yale)