Courses Offered

Below is a list of upper-level Theory courses being taught in this Fall and Winter. More information about these courses and others, including prerequisite information, can be four on the EECS courses page of the Michigan Engineering Bulletin.

Fall 2024

EECS 475: Introduction to Cryptography

Instructor: Ke Wu

Covers fundamental concepts, algorithms, and protocols in cryptography. Topics: ancient ciphers, Shannon theory, symmetric encryption, public key encryption, hash functions, digital signatures, key distribution. Emphasizes attack models, precise definitions of security, reductions, and proof techniques.

EECS 477: Introduction to Algorithms

Instructor: Euiwoong Lee

Fundamental techniques for designing efficient algorithms and basic mathematical methods for analyzing their performance. Paradigms for algorithm design: divide-and-conquer, greedy methods, graph search techniques, dynamic programming. Design of efficient data structures and analysis of the running time and space requirements of algorithms in the worst and average cases.

EECS 498: Advanced Data Structures

Instructor: Seth Pettie

EECS 498/CSE 598: Algorithms for Machine Learning and Data Science

Instructor: Michał Dereziński  

This course will introduce algorithmic and theoretical foundations of data science, with a focus on applications to machine learning. With the emergence of machine learning and data science, as well as the ever-increasing data sizes, providing theoretical foundations for the computational complexity of data manipulation algorithms is becoming increasingly important. The course will cover several important algorithms which use randomization and linear algebra to construct compressed data representations and efficiently perform prediction, optimization and inference tasks for big data and ML. We will introduce randomized dimensionality reduction, sketching, and stochastic optimization, among others, and provide the tools needed to design and analyze algorithms that rely on these concepts. Algorithmic paradigms for big data The course will delve into topics in linear algebra, such as matrix multiplication and singular value decomposition, as well as in probability, such as expectation, independence and concentration of random variables.

CSE 572: Randomness and Computation

Instructor: Nikhil Bansal

Fundamentals of randomness and its pervasive use in computer science, including the probabilistic method, the design and analysis of algorithms, computational complexity, cryptography, combinatorics, logic and proof systems, and related topics.

CSE 575: Advanced Cryptography

Instructor: Paul Grubbs

A rigorous introduction to the design of cryptosystems and to cryptanalysis. Topics include cryptanalysis of classical cryptosystems; theoretical analysis of one-way functions; DES and differential cryptanalysis; the RSA cryptosystem; ElGamal, elliptic, hyperelliptic and hidden mononomial cryptosystems; attacks on signature schemes, identification schemes and authentication codes; secret sharing; and zero knowledge.

CSE 598: Foundations of Fairness in Machine Learning

Instructor: Ben Fish

Winter 2025

EECS 475: Introduction to Cryptography

Instructor: Mahdi Cheraghchi

Cryptography, or “secret writing,” is nearly as old as written communication itself. Yet only in the past few decades has it grown from a “black art” into science with rigorous mathematical foundations and methodologies. These have taken cryptography far beyond its roots in simple secret codes, to a discipline with wide-reaching influence on computing as a whole. This class is an undergraduate-level introduction to modern cryptography. The emphasis is on essential concepts, precise attack models and security definitions, and constructions of some real-world cryptosystems. For more information, see the course website.

477: Introduction to Algorithms

Instructor: Thatchaphol Saranurak

Fundamental techniques for designing efficient algorithms and basic mathematical methods for analyzing their performance. Paradigms for algorithm design: divide-and-conquer, greedy methods, graph search techniques, dynamic programming. Design of efficient data structures and analysis of the running time and space requirements of algorithms in the worst and average cases.

NEW — EECS 498: Computability and Complexity

Instructor: Nikhil Bansal

Computability and Complexity Theory are the foundational pillars of computation theory. They investigate which problems can be solved at all, or solved within constraints on resources such as time and space. In this course, we will explore various computational models, including finite automata, Turing machines, RAM machines, and Boolean circuits, and study complexity classes such as P, NP, co-NP, PSPACE, and co-NL. The goal is to develop a deeper understanding of fundamental computational questions and the objects within the computational universe, while also learning techniques to reason about them. For more information, see the course flyer.

CSE 574: Computational Complexity Theory

Instructor: Mahdi Cheraghchi

This course explores the story of computation after Alan Turing. The notion of Turing Machines provides a mathematical abstraction of what it means to compute. In principle, it captures all computing devices that we know of or will ever come up with. Computational complexity takes a step further and also takes into consideration the fact that computers are limited in resources, such as time, memory, or randomness. The phenomenon of computing becomes much more nuanced with limited resources in mind. Which computational problems can or cannot be solved with limited resources? That is what computational complexity aims to study. For more information, see the course website.

CSE 586: Design and Analysis of Algorithms

Instructor: Quentin Stout

Design of algorithms for nonnumeric problems involving sorting, searching, scheduling, graph theory and geometry. Design techniques such as approximation, branch-and-bound, divide-and-conquer, dynamic programming, greed and randomization applied to polynomial and NP-hard problems. Analysis of time and space utilization.

CSE 598: Machine Learning Theory

Instructor: Wei Hu

NEW — CSE 598: Graph Algorithms

Instructor: Nicole Wein

Graphs are ubiquitous throughout computer science (and beyond). In this course we will mainly focus on combinatorial algorithms for fundamental graph problems. The results we’ll cover range from classic results (1970s) to exciting recent developments (2020s). Topics will be drawn from the areas of approximation in P, dynamic algorithms, parameterized algorithms, and fine-grained complexity. For more information, see the course flyer.

CSE 598: Approximation Algorithms

Instructor: Euiwoong Lee

Most interesting optimization problems are NP-hard, so unless P = NP, there are no polynomial time algorithms to find optimal solutions to such problems. Therefore, it is natural and important to study approximation algorithms that compute approximately optimal solutions with provable guarantees; there are also hardness of approximation results, showing that even an approximation is NP-hard beyond a certain threshold. This course will cover both approximation algorithms and hardness of approximation results for fundamental optimization problems, stressing tools required to prove both algorithms and complexity results.

NEW — CSE 598: Foundation of Distributed Consensus and Blockchain

Instructor: Ke Wu

This course covers the  mathematical foundations and principles/theory for blockchains, including the following modules that form the scientific foundation of blockchain technologies: distributed consensus, blockchain protocols, and incentives and mechanism design. For more information, see the course flyer.