FoCM Workshop 12: Algorithmic Game Theory and Metric Embeddings

FoCM Workshop 12

Relations with Computer Science: Algorithmic Game Theory and Metric Embeddings
July 4-6, 2005, Santander, Spain.
This is one of 20 workshops that make up the FoCM 2005 conference. The focus of this workshop is on Algorithmic Game Theory and Metric Embeddings, two areas in which Computational Mathematics and Computer Science have close connections. A third theme of this workshop is Approximation Algorithms, a central topic in computer science that is closely related to both of these areas. For local and conference information, see the conference webpage.
ORGANIZERS:

Allan Borodin (University of Toronto)
Avrim Blum (Carnegie Mellon University)

TENTATIVE SCHEDULE:
July 4:

Block 1 [1:50-2:35]

Yossi Azar
The Price of Routing Unsplittable Flow

Block 2 [2:40-3:25]

Kamal Jain
An application of market equilibrium in distributed load balancing in wireless networking

BREAK [3:25-4:00]

COFFEE BREAK

Block 3 [4:00-4.45]

Berthold Voecking [SEMI-PLENARY]
Approximation Techniques for Utilitarian Mechanism Design

Block 4 [4.50-5.35]

Jason Hartline
Derandomization of Auctions

Block 5 [5.40-6.25]

Discussion/open problems

July 5:

Block 1 [1:50-2:35]

Avrim Blum
On Routing without Regret

Block 2 [2:40-3:25]

Tim Roughgarden
Computing (Correlated) Equilibria in Multi-Player Games

BREAK [3:25-4:00]

COFFEE BREAK

Block 3 [4:00-4.45]

Santosh Vempala
Nash Equilibria in Random Games

Block 4 [4.50-5.35]

Michael Kearns [SEMI-PLENARY]
The Effects of Network Structure on Equilibria and Computation

Block 5 [5.40-6.25]

Discussion/open problems

July 6:

Block 1 [1:50-2:35]

Anupam Gupta
Metric Embeddings into l_1 and the Sparsest Cut Problem

Block 2 [2:40-3:25]

Avner Magen
Metric Variance

BREAK [3:25-4:00]

COFFEE BREAK

Block 3 [4:00-4.45]

Yuval Rabani
On Earthmover Distance, Metric Labeling, and 0-Extension

Block 4 [4.50-5.35]

Vijay Vazirani
Adwords and Generalized Online Matching

Block 5 [5.40-6.25]

Piotr Indyk [SEMI-PLENARY]
Approximations and streaming algorithms for geometric data

Note: there will also be related plenary talks at the conference by Eva Tardos and Shang-Hua Teng.

Block 1 [1:50-2:35]	Yossi Azar The Price of Routing Unsplittable Flow
Block 2 [2:40-3:25]	Kamal Jain An application of market equilibrium in distributed load balancing in wireless networking
BREAK [3:25-4:00]	COFFEE BREAK
Block 3 [4:00-4.45]	Berthold Voecking [SEMI-PLENARY] Approximation Techniques for Utilitarian Mechanism Design
Block 4 [4.50-5.35]	Jason Hartline Derandomization of Auctions
Block 5 [5.40-6.25]	Discussion/open problems

Block 1 [1:50-2:35]	Avrim Blum On Routing without Regret
Block 2 [2:40-3:25]	Tim Roughgarden Computing (Correlated) Equilibria in Multi-Player Games
BREAK [3:25-4:00]	COFFEE BREAK
Block 3 [4:00-4.45]	Santosh Vempala Nash Equilibria in Random Games
Block 4 [4.50-5.35]	Michael Kearns [SEMI-PLENARY] The Effects of Network Structure on Equilibria and Computation
Block 5 [5.40-6.25]	Discussion/open problems

Block 1 [1:50-2:35]	Anupam Gupta Metric Embeddings into l_1 and the Sparsest Cut Problem
Block 2 [2:40-3:25]	Avner Magen Metric Variance
BREAK [3:25-4:00]	COFFEE BREAK
Block 3 [4:00-4.45]	Yuval Rabani On Earthmover Distance, Metric Labeling, and 0-Extension
Block 4 [4.50-5.35]	Vijay Vazirani Adwords and Generalized Online Matching
Block 5 [5.40-6.25]	Piotr Indyk [SEMI-PLENARY] Approximations and streaming algorithms for geometric data