Prof. Vijay V. Vazirani has been honoured with the prestigious KnowDis Award of Excellence
for 2022 for his fundamental contributions to algorithm design and computer science theory,
announced KnowDis AI’s CEO, Saurabh Singal. Previous recipients include Prof PCP Bhatt,
Prof SN Maheshwari, and SPIC-MACAY-founder Prof Kiran Seth. Vazirani is currently a
Distinguished Professor at the University of California, Irvine.
A trailblazer
Vijay Vazirani is among the most distinguished researchers in the field of Computer Science,
having made highly consequential contributions in the areas of Combinatorial Optimization,
Computational Complexity Theory, Approximation Algorithms, Algorithmic Game Theory, and
Matching-Based Market Design. He has worked alongside luminaries like Manuel Blum, Richard
Karp, Micahel Rabin, and Leslie Valiant. He received the INFORMS John von Neumann Theory
Prize in 2022. This is one of the most prestigious prizes in the mathematical sciences and is
awarded to a scholar whose contributions have stood the test of time.
Early Life and Education
Vijay Vazirani was brought up in New Delhi, and his schooling was at the Springdales Public
School, Pusa Road. Vijay’s mother had a profound passion for classical music, which she
shared with her son. Vijay’s father, a Professor of Civil Engineering, shared his quick, intuitive
solutions to complex maths problems with him. Young Vijay grew up interested in electronics
and constantly tinkered with radios and transistors as a child. These varying interests and
influences shaped Vijay’s mind in his formative years and left a lasting impression as he
achieved great prominence as a leading computer scientist worldwide. It is worth mentioning
that Vijay’s brother Umesh is also a distinguished scholar and one of the leading researchers in
Quantum Computing.
After finishing school, Vijay joined IIT Delhi’s B.Tech programme in Electrical Engineering. Even
as a first-year student, he reached out to fifth-year seniors, who shared their computer
programming coursework with him. During that period, he developed a keen interest in
computing and decided that he liked CS more than EE; however, CS was not offered to
undergraduates at IITD. Despite the scarcity of books and equipment, he pursued his interest.
Initially, he relied on a massive British ICL computer in the basement of the computer centre at
IIT Delhi, and he used punched cards for programming it. Later, Prof PCP Bhatt, noting his
interest in computing, arranged for him to use a PDP 11, usually meant only for masters-level
students and research. Eventually, he transferred to MIT, receiving his bachelor’s degree in
computer science.
Research Career after MIT
After MIT, where he did his undergraduate thesis in AI, Vazirani moved to UC Berkeley for a
PhD and shifted to theoretical computer science. During his first year as a PhD student, Vazirani
and fellow student Silvio Micali discovered what is still the most efficient known algorithm for the
classical maximum matching problem in general graphs. Although the algorithm was published
in 1980, the (difficult) question of giving a proof of correctness remained open. Indeed, this
problem has occupied Vazirani’s mind ever since. Very recently, he completed a paper giving
the first complete and correct proof; however, the paper is yet to be published. Such a passage
of time is not unusual in mathematics; it is well-known that the proof of some sphere-packing
conjectures and Fermat’s last theorem took several centuries.
A visionary in algorithmic game theory
Vazirani stands as one of the architects of Algorithmic Game Theory, specifically focusing on the
computational aspects of market equilibria. His co-edited book Algorithmic Game Theory played
a crucial role in its quick growth. In 1990, Vazirani co-authored a paper giving an optimal
algorithm for the online bipartite matching problem. In this scenario, the underlying graph
unfolds vertex by vertex, necessitating instantaneous matching without foresight into future
arrivals. This paper’s applicability extends to various matching markets on the Internet, such as
Google’s AdWords market, Uber, and Airbnb, in which online decision-making plays a pivotal
role, establishing it as a paradigm in this field; interestingly, the paper was published in
pre-Internet days! Keenly aware of these new applications, Vazirani was one of the first
researchers to realise that the area of matching-based market design, initiated by the seminal
1962 paper of Gale and Shapley, had entered its “second life”. Over the last few years, he has
played a leadership role in fostering this area and informing the research community at large
about it via scientific programs and a new comprehensive co-edited book, Online and
Matching-Based Market Design.
The innovator of algorithms
Beyond this, Vazirani is also renowned for his work on approximation algorithms, which help
deal with the intractability inherent in numerous optimisation problems of practical importance.
His contributions span diverse fundamental problems, including set covering, survivable network
design, multicommodity flow, multicut, k-cuts, facility location, and k-medians. These efforts
culminated in his now-classic book, Approximation Algorithms.
Educator and mentor
Beyond his groundbreaking research, Vijay Vazirani is known for his dedication to education and
mentorship. He is a passionate follower of the Socratic teaching style — always drawing in his
students and audience into an active dialogue — and is deeply committed to helping his
students understand complex concepts in simple ways. The same holds for writings. A couple of
decades ago, Approximation Algorithms was considered a complex area. Yet, his classic book
on this topic is so lucid that even undergraduate students can absorb its content today. Many of
his former PhD students have become influential figures in academia and industry. One notable
example is Naveen Garg, Professor of Computer Science at IIT Delhi and a Bhatnagar Award
winner.
A family man, philanthropist and a passionate music-lover
Vijay is known for his warm and approachable demeanour. Colleagues and friends describe him
as not only a brilliant scientist but also a compassionate and humble individual. He is connected
to the Akshaya Patra Foundation, which has done great work on fighting classroom hunger. He
is a loving husband and father, finding a balance between his professional and personal life.
Vazirani indulges in another passion — music. His involvement in fine Indian classical music,
Hindustani and Carnatic, Western classical music, and Jazz is a source of inspiration in his
journey through complex algorithmic ideas.
About KnowDis AI
KnowDis is an innovative AI startup founded by Saurabh Singal, a former hedge fund manager
and an alumnus of IIT Delhi and Carnegie Mellon University. KnowDis is well known for its
world-beating NLP products, including recommendation systems and machine translation
software. KnowDis AI models power IndiaMART’s B2B platform. KnowDis is also involved in
drug discovery using Artificial Intelligence.
