• Explore
    • Contact Us
  • Faculty
  • Research
    • Research Areas
    • Research Centers
  • Graduate Degrees
    • Computer Science Programs
    • Current Graduate Students
  • Undergraduate Degrees
  • News & Events
    • News
    • Seminar Series
    • Distinguished Lecture Series
    • Research Showcase
  • Apply Now
    • Undergraduate Admissions
    • Graduate Admissions
    • Faculty Candidates

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

June 11, 2018

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

« Professor Franz Receives UCI Applied Innovation’s Inaugural Innovator of the Year Award
Professor Jain Receives IEEE Award for Article on Social-Sensed Multimedia Computing »

Latest news

  • 2022 Butterworth Product Development Competition: Back in Full Swing! June 23, 2022
  • Computer Science Researchers Collaborating on $1.2M NSF Grant to Study Geometric Graphs June 16, 2022
  • UCI News: “UCI wins 5-year, $14M NIH grant to study brain circuits susceptible to aging, Alzheimer’s disease” (Gopi Meenakshisundaram mentioned) June 14, 2022
  • Pierre Baldi Tackles Deep Learning at 800th Anniversary of the University of Padova in Italy June 6, 2022
  • The Conversation: “What are digital twins? A pair of computer modeling experts explain” (Co-author: Nalini Venkatasubramanian) June 1, 2022
  • © 2022 UC Regents
  • Feedback
  • Privacy Policy