ICS News Archive

Faculty Spotlight: Vijay Vazirani’s Contributions Stand the Test of Time

The INFORMS John von Neumann Theory Prize is awarded annually to a scholar who has made fundamental contributions to theory in operations research and the management sciences — “contributions that have stood the test of time.” The 2022 prize was awarded to Vijay Vazirani for his sustained and significant research into the design of algorithms, including approximation algorithms, computational complexity theory, and algorithmic game theory. Vazirani, a Distinguished Professor of Computer Science in UC Irvine’s Donald Bren School of Information and Computer Sciences (ICS), talks about receiving this award. He also discusses his current research and his role as director of the ACO Center @ UCI, an interdisciplinary research center focused on algorithms, combinatorics and optimization. But first, we learn what drew him to the field of computer science.

What sparked your interest in computer science?
In high school, I used to assemble radio sets and transistors. I was very much attracted to the new fields of electronics and superconductors and so on. Toward the end of high school, I was fascinated to see an electronic calculator at a Soviet science exhibition in Delhi. It was infinitely more powerful and convenient than the slide-rule I was using for calculations. Suddenly, a whole new world seemed to open up!

As a first-year electrical engineering student at IIT Delhi [the Indian Institute of Technology, Delhi], I started talking to the fifth-year students who were studying Fortran programming from a very famous book of the day by Daniel McCracken (in those days, there were hardly any books on programming). Although IIT Delhi didn’t offer a major in computer science, it had a computer — a massive British ICL computer that took up an entire room in the computer center in the basement. You programmed it using punched cards, and its output came on huge sheets of paper. The output would typically have an error, and then you’d have to go back and change a few cards. Again, huge sheets of paper would come out. Any student could go and use it, fortunately. So, that’s how I started programming.

At the end of my first year, I spent my entire summer holiday programming. At that point, I loved computers, and I loved programming. I loved everything about it. By the time I was in my second year, I started talking to the master’s students at IIT. Their professor allowed me to use a lab that was really meant for master’s students — I was the only bachelor’s student there. The lab had an American PDP 11 on which I ran programs written in machine and assembly languages.

At the end of my second year, one of my fellow students transferred to MIT to study computer science. That gave me the idea of attempting the same. I spent the entire third year taking exams, applying to many places in the U.S. and arranging for funds and immigration. It was a full-time job, in addition to my coursework, but at the end of my third year, I got admission at MIT as well as a green card to come to the U.S.

How was that transition for you?
It was very exciting but also quite difficult because the style of thinking was different; it was more abstract and much deeper. And I was surrounded by geniuses, so it was intimidating and exciting all at the same time. I was doing CS, which I liked much more than EE, and that was great. In the two years I spent at MIT, I took mostly CS courses together with a few humanities and math courses — I didn’t have to take any courses that I didn’t like. I did my undergraduate thesis on AI. However, after my undergrad, I decided to move to theory and joined UC Berkeley for a Ph.D.

Can you talk about your main research focus and its practical applications?
The underlying theme has always been the design of efficient algorithms. Through the years, I worked on many of its aspects — combinatorial optimization, randomized algorithms, approximation algorithms, online algorithms, and algorithmic game theory. Over the last two decades, my work has been at the boundaries between disciplines: algorithm design, game theory and economics, and operations research and mathematical programming. These boundaries contain beautiful, nascent issues for study, with much potential for impact.

When I came to UCI, almost six years ago, I looked for a new research direction and settled on algorithms for matching markets, since I had worked extensively on the classical matching problem as well as on the computability of market equilibria; this area is also highly interdisciplinary. Matching markets have numerous applications — the AdWords market of Google and matching markets on the Internet, e.g., Uber, Airbnb, Match.com and Upwork.

And any new projects you’re working on?
Over the last two years, I have been exploring a very important solution concept in game theory called the “core of a game.” On this topic, which is more than half a century old, I seem to have basic new results, as outlined in two recent papers: LP-Duality Theory and the Cores of Games and The General Graph Matching Game: Approximate Core. This notion is also covered in my upcoming co-edited book, Online and Matching-Based Market Design.

What was your reaction to receiving the INFORMS John von Neumann Theory Prize?
Considering von Neumann’s towering legacy and the stellar list of past awardees, including Nobel Laureates Kenneth Arrow, John Nash and Lloyd Shapley, this was a great honor and one of the most important moments in my career. It’s nice to get recognition, but I should quickly add that my main satisfaction comes from the work itself.

Awards do serve the purpose of underlining important works and important researchers, thereby providing guidance to future researchers. The big awards, and biographies of those awardees, also serve to inspire children at an early stage; this was certainly true in my case.

Speaking of serving a purpose, on your homepage, you link to “a worthy cause.” Can you elaborate on that?
The Akshaya Patra Foundation is an important organization in India which has done great work on fighting classroom hunger. I contribute to it because I know the money will be very effectively spent on a good cause: for just $12, you can feed a kid for an entire year. That’s because the organization cooks their own food every day — rice and beans and vegetables, nothing fancy — and they take it to the schools to distribute it. So many students would otherwise go hungry; it lifts everything, including the education given to these kids.

Can you also talk about your role as director of the ACO Center @ UCI?
The Center brings together scholars from three different departments: the Computer Science Department, the Math Department, and the Business School.

I love the seminar series we’re hosting, and so do the students. There’s something very interesting and exciting happening every week. The students enthusiastically attend them on a regular basis because they get a very broad introduction to many different aspects of theory and related areas. Many of them also meet the visitors and obtain valuable feedback on their research projects. Several faculty members also attend the seminars, and they find them a great way of keeping up to date with the latest research developments.

In the last couple of years, several research projects were launched together with the visiting scholars, e.g. in January, Martin Bullinger visited from Munich for a month and gave a seminar, and now he has two ongoing collaborations with me and my students.

Through the center, I got to know a student from UCI’s School of Business, Mojtaba Hosseini. Our joint paper was published in the conference Innovations in Theoretical Computer Science and was recently submitted to Operations Research, which is the flagship journal of the OR community. This work played a role in Hosseini’s job offer from the University of Iowa, where he is now.

The center has really become a hub for interdisciplinary research at UCI.

— Shani Murray