ICS News Archive

New Faculty Spotlight: Professor Vijay Vazirani Continues Groundbreaking Research

Vijay Vazirani, Distinguished Professor of Computer Science, joined the ICS faculty in Fall 2017.

Q: Can you tell us about your background?
I started my undergraduate studies in electrical engineering at the Indian Institute of Technology, Delhi (ITTD). The institute didn’t have a major in computer science at the time, but after talking to master’s students in the field, I started programming in the computer center and studying related topics on my own. In my second year, I realized I really wanted to study computer science, so I applied to U.S. universities and managed to get admission at MIT. The curriculum at MIT was of course a quantum leap beyond IITD, and I was thrilled to be studying CS.
I then went to the University of California, Berkeley for my Ph.D., which is when I realized I wanted to end up here in California. After my Ph.D. though, I moved around a bit, doing my postdoc at Harvard and even teaching in India at ITTD. In 1995, I started teaching at Georgia Tech, which is where I remained for the next 22 years.

Q: What brought you to UCI?
This fall, my son joined Columbia University for his undergrad, and that gave me the chance to move to California. I view the move to UCI as a huge opportunity, because it is a fantastic university with top-notch researchers. Moreover, CS at UCI is on a clear upward path and I look forward to being part of this exciting period of growth. In the 22 years I was at Georgia Tech, its ranking in CS went up from 35 to 9, with the Theoretical Computer Science Group being ranked at number 7.

Q: What courses will you be teaching this year?
This winter, I’ll be teaching a graduate-level course on approximation algorithms, a subarea within theoretical computer science. The starting point will be my book, Approximation Algorithms (Springer, 2001).

Q: You have made seminal contributions to the theory of algorithms. Can you talk about some of the applications of your work?
One application area is the AdWords market of Google. Via this multibillion dollar market, Google sells keyword queries to advertisers. To maximize its revenue, Google would have simply sold each query to the highest bidder; however, there are additional complications because of the daily budgets declared by advertisers. My co-authors and I gave an (optimal) online algorithm for this problem. The algorithm has a very small overhead and, for this reason, it is easy to implement on top of existing systems and is used by most search engine companies.
This summer, I worked with Nima Anari, a postdoctoral fellow at Simons Institute in Berkeley, and we managed to solve a problem that was open for over 30 years. We gave a deterministic fast parallel algorithm for finding a perfect matching in a planar graph.

Q: What do you do in your spare time?
I enjoy listening to music. I’ve attended several concerts at UCI’s Winifred Smith Hall and Barclay Theater, and I plan to make full use of the campus calendar. The events I have been to were excellent!

Q: Is there a book you wish everyone would read?
I would highly recommend The Master of Go (Vintage, 1996) by Japanese author Yasunari Kawabata, who won the 1968 Nobel Prize in Literature. This is an absolutely fascinating novel about a days-long contest between an old master of the ancient board game of “Go” and his young challenger.