CS/ECE 374: Algorithms (I)
(with Prof. Chan).
CS/ECE 374 covers fundamental tools and techniques from theoretical computer science, including design and analysis of algorithms, formal languages and automata, computability, and complexity. Specific topics include regular and context-free languages, finite-state automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth- and breadth-first search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NP-completeness.
CS 473: Algorithms (II)
A list of high-level topics that we hope to cover (this list is tentative): Divide and conquer, FFT. (Advanced) Dynamic Programming. Shortest path algorithms and negative cycle detection. Randomization in algorithms and data structures. Network flows and applications. Matchings. Basics of linear and convex programming. NP-Completeness and reductions. Basics of approximation and online algorithms.
CS 598 RM: Algorithmic Game Theory
Algorithmic game theory has become more relevant than ever before with the advent of online markets, ad auctions, social networks, and recommendation systems, where rational agents interact to achieve selfish goals. The last two decades have witnessed the development of a rich theory in this area and deep mathematical connections have been established. The first half of the course will provide a broad introduction to games and market models, solution concepts, classical as well as recent developments in the field on equilibrium computation & complexity, mechanism design, price of anarchy, matching markets, game dynamics, and others. The second half will address a selection of advanced topics and research projects.
At Georgia Tech
CS 8803: Advanced Topics in Algorithmic Game
Co-taught with Jugal Garg and Georgios Piliouras
A research oriented course focusing on the intersection of
computer science and game theory. During the first half of the course, the
participants will be exposed to key ideas and results from algorithmic game
theory. In the second part we will be exploring research tangents, looking
into open questions and working on formulating novel problems.
Co-taught with Vijay V. Vazirani
Among the most novel and significant additions to the theory of algorithms and computational complexity over the last decade has been deep insights into the computability of equilibria, both Nash and market. In this course we will cover various algorithmic and hardness results for Nash and market equilibrium computation.