84. Mathematical Colloquium
Vijay V. Vazirani
Georgia Institute of Technology
First talk
NEW (PRACTICAL) COMPLEMENTARY PIVOT ALGORITHMS FOR MARKET EQUILIBRIA
July 5, 2013, 11:00room S3, 3rd floor
Malostranské nám. 25
118 00 Praha 1
Abstract
Complementary pivot algorithms, in the style of the simplex algorithm, tend to work well in practice despite having an exponential worst case behavior - a case in point being the classic Lemke-Howson algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and yields deep structural insights, such as oddness of the number of equilibria.
Our first result accomplishes all of the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise linear concave utilities. Our second result extends this to markets with production.
Based on the following paper, and a recent joint work with Jugal Garg and Ruta Mehta: SPLC.pdf
Second talk
MATCHING - A NEW PROOF FOR AN ANCIENT ALGORITHM
July 6, 2013, 10:30room S6, 2nd floor
Malostranské nám. 25
118 00 Praha 1
Abstract
For all practical purposes, the Micali--Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a "black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm: http://arxiv.org/abs/1210.4594
In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.
About the speaker
Vijay V. Vazirani studoval informatiku na MIT, Kalifornske universite v Berkeley and na Harvardske universite (kde jeho skoliteli byli M. Blum and M. Rabin). Ziskal tez prestizni President Young Investigator Award. Posleze byl zamestnan na prednich institucich v USA a v Indii (IBM, Cornell, Caltech, AT$&T Murray Hill, MSRI Berkeley). Od roku 1995 je radnym profesorem na Fakulte Informatiky v Georgia Institute of Technology. Jeho vedecka prace se vyznacuje nebyvalou siri vpodstate v cele informatice vcetne socialnich aspektu discipliny. V teto souvislosti byl napriklad opakovane hostem laboratore SISL (Social and Information Sciences Laboratory) na CalTechu.
Vijay je autorem vice nez 100 clanku z teorie algoritmu (vcetne znamych algoritmu pro parovani), teorie slozitosti, pribliznych algoritmu a mnoha praci venovanych algoritmum pro trh a trzni rovnovahu (tzv. market equilibria) a algoritmicke teorii her. Je autorem nekolika knih vcetne popularnich Approximation Algorithms (Springer 2001). Vazirani je editorem 3 mezinarodnich casopisu a autorem nekolika patentu. Dostal nekolik mezinarodnich oceneni, jmenujme napr. Googgenheim Fellowship a rovnez byl v roce 2005 zvolen ACM Fellow. Prof Vazirani je znam jako vyborny prednasejici. Ekonomicky motivovana informatika je v posledni dobe v centru jeho pozornosti a je take nametem jeho prazskeho kolokvia.
