Professor Vazirani Receives $500K in NSF Funding for New Research into Algorithms

Distinguished Professor of Computer Science Vijay Vazirani recently received a grant of $500,000 from the National Science Foundation (NSF) for his proposal, “Algorithms for Matching, Markets, and Matching Markets.” All three problem areas — matching, markets, and matching markets — have deep and rich algorithmic theories and numerous applications. For example, applications of matching markets range from assigning interns to hospitals, to assigning query keywords to advertisers in the multibillion-dollar online ads markets of search engine companies such as Google. Over the years, Vazirani has made foundational contributions to all three problem areas, and in the current proposal, he has identified several new problems.

Last year, Vazirani solved a 30-plus-year-old problem by giving a fast parallel (NC) algorithm for finding a perfect matching in planar graphs; several of his open problems on matching arise from this work. On the computability of market equilibria, one of Vazirani’s main results was giving complementary pivot equilibrium algorithms for several market models. He has proposed analyzing the smoothed complexity of these algorithms. His recent work on the stable matching problem has yielded new structural results about relationships between the lattices of stable matchings of two “nearby” instances. This should help in developing efficient algorithms for finding solutions that are robust to errors introduced in the input.

Vazirani, who joined the ICS faculty in fall 2017, has the mandate of helping propel UCI’s Theory Group to the next level. To this end, he will be recruiting a postdoc as well as high-quality graduate students to increase the level and quality of research activity, and will also help revamp graduate and undergrad theory courses.

— Shani Murray