# Colloquium

## Joint ARC and School of Math Colloquium by Noga Alon, Tel Aviv University, Israel

Date:
Thu, 2012-09-06 11:00
Location:
Klaus 1116

Title: Coloring Random Cayley Graphs

Abstract:

## ARC Colloquium: Shachar Lovett, Institute of Advanced Study, Princeton, NJ

Date:
Mon, 2012-09-10 13:00
Location:
MiRC 102A

Title: Constructive Discrepancy Minimization by Walking on The Edges

Abstract:

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of $n$ sets in a universe of size $n$, there always exists a coloring which achieves discrepancy $6\sqrt{n}$. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring.

## ARC5 - Distinguished Lecture by Noga Alon, Tel Aviv University, Israel and Persi Diaconis, Stanford University

Date:
Tue, 2012-08-28 09:00
Location:
Klaus 1116

Speaker: Noga Alon, Tel Aviv University

Title: On graphs, arithmetic progressions and communication

Abstract:

Tools from Extremal Graph Theory are helpful in the study of problems in Additive Number Theory, Theoretical Computer Science, and Information Theory. I will illustrate this fact by several closely related examples focusing on a recent one in a joint paper with Moitra and Sudakov.

Speaker: Persi Diaconis

Title: "An Introduction to additive combinatorics via 'carries'"

Abstract

## ARC Colloquium: Devavrat Shah, MIT

Date:
Thu, 2012-05-31 15:00
Location:
Klaus 1116W

Abstract

## ARC Colloquium: Sebastian Lahaie, Yahoo! Research

Date:
Mon, 2012-04-16 13:00
Location:
MiRC 102A

Title: A Kernel-Based Combinatorial Auction

## Jason Hartline, Northwestern University

Date:
Mon, 2012-04-23 13:00
Location:
Klaus 1116

Title: The Simple Economics of Approximately Optimal Auctions

## ARC Colloquium: Vijay V. Vazirani, Georgia Tech

Date:
Wed, 2012-01-18 15:00
Location:
MiRC 102A Georgia Tech

Abstract: Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Fisher and Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case.

## ARC Colloquium: Yashodhan Kanoria, Stanford University

Date:
Mon, 2012-02-13 13:30
Location:
MiRC 102A Georgia Tech, Atlanta, GA

Abstract:

In many contexts, agents 'learn' behavior from interaction with friends/neighbors on a network. We call this phenomenon 'social learning'. We will focus on models of repeated interaction, with agents 'voting' in a series of rounds on some issue of interest. Votes in the initial round are based on 'private signals', whereas votes in future rounds incorporate knowledge of previous votes cast by friends.

## ARC Colloquium: Constantinos Daskalakis (MIT)

Date:
Mon, 2012-03-26 13:00
Location:
Klaus 1116 W, Georgia Tech, Atlanta, GA

Abstract:

Title: Multidimensional Revenue Optimization

In his seminal paper, Myerson [1981] provided a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient.

(joint work with Yang Cai and Matt Weinberg)