Umesh Vazirani

Umesh Vazirani
University of California, Berkeley

Making Google Richer: Optimal Algorithms for the AdWords Auction
Abstract: This year the combined advertising revenues of Google and Yahoo is expected to rival the combined prime-time ad revenues of America's three big television networks, ABC, CBS, and NBC. The key to this revolution in advertising is an innovative auction run by the search engine companies. Companies' bids for search keywords determine which ads are displayed during Internet searches. There are a number of algorithmic and game theoretic issues that arise in this context. In particular, the problem of maximizing revenue in such keyword auctions can be formulated as an online computational problem. I will describe two simple algorithms that achieve optimal performance. The proofs of performance of these algorithms rely on a new linear programming based technique called tradeoff revealing family of LPs, which I will briefly touch upon.

The talk is based on joint work with Aranyak Mehta, Amin Saberi and Vijay Vazirani. 

Biography: Umesh Vazirani is a Professor in the Computer Science Division of the Department of Electrical Engineering and Computer Science at UC Berkeley. He received an NSF Presidential Young Investigator Award in 1987 and the Friedman Mathematics Prize in 1985. He has written the book, An Introduction of Computational Learning Theory (with Michael Kearns), and currently is at the forefront of research in the area of quantum computing.

Professor Vazirani is a Director of the Berkeley Quantum Information and Computation Center (BQIC).

Quick Links

2012-2013 DLS

  • Zvi Galil
  • Hector Levesque
  • Jennifer Chayes
  • Renée Miller
  • Maneesh Agrawala
  • David Eppstein

2011-2012 DLS

  • Bruno Buchberger
  • Saul Greenberg
  • Ed Lazowska
  • Jeannette Wing
  • Cynthia Dwork

2010-2011 DLS

  • Stuart Feldman
  • Madhu Sudan
  • Susan Landau
  • Gilles Brassard
  • Joe Marks
  • Jon Kleinberg

2009-2010 DLS

  • Andy Yao
  • Paul Van Oorschot
  • Shafi Goldwasser
  • Adi Shamir
  • Fran Allen

2008-2009 DLS

  • Alan Kay
  • Eric Brewer
  • Anne Condon
  • Nancy Leveson
  • Tom Furness

2007-2008 DLS

  • David Patterson
  • Manuela Veloso
  • David D. Clark
  • Christos Papadimitriou

2006-2007 DLS

  • Kurt Mehlhorn
  • Ben Shneiderman
  • Barbara Liskov
  • Vint Cerf

2005-2006 DLS

  • Umesh Vazirani
  • Stephen Cook
  • Andrew Tanenbaum
  • Andries van Dam

2004-2005 DLS

  • Alfred Aho
  • Brian Kernighan
  • Jim Gray
  • Barbara Grosz
  • Jim Mitchell