All reports by Author Tim Roughgarden:

__
TR18-001
| 2nd January 2018
__

Tim Roughgarden#### Complexity Theory, Game Theory, and Economics

__
TR16-055
| 11th April 2016
__

Tim Roughgarden, Omri Weinstein#### On the Communication Complexity of Approximate Fixed Points

__
TR15-156
| 21st September 2015
__

Tim Roughgarden#### Communication Complexity (for Algorithm Designers)

__
TR15-153
| 21st September 2015
__

Tim Roughgarden#### Computing Equilibria: A Computational Complexity Perspective

Tim Roughgarden

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 >>>

Tim Roughgarden, Omri Weinstein

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 >>>

Tim Roughgarden

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 >>>

Tim Roughgarden

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 >>>