This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.
The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>
We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition
of two Lipschitz functions g\circ f : [0,1]^n \to [0,1]^n, where Alice holds f and Bob holds g. We prove an
exponential (in n) lower bound on the deterministic ...
more >>>
This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at
Stanford in the winter quarter of 2015. The two primary goals of the course are:
1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>
Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.
... more >>>