Vijay Vazirani
Encyclopedia
Vijay Virkumar Vazirani
( ; b. 1957) is an Indian American
Professor of Computer Science at Georgia Tech
.
He received his Bachelor's degree
from MIT in 1979 and his Ph.D.
from the University of California, Berkeley
in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian Institute of Technology, New Delhi
. Vijay Vazirani was also a McKay Visiting Professor at the University of California, Berkeley
.
, cryptography
, coding theory
, and game theory
.
During the 1980s, he made important contributions to the classical maximum matching problem. During the 1990s he worked mostly on approximation algorithms, championing the primal-dual schema, which he applied to problems arising in network design, facility location and web caching, and clustering. In July 2001 he published a book on approximation algorithms (Springer-Verlag, Berlin).
One of his significant research results was proving, along with Leslie Valiant
, that if UNIQUE-SAT is in P
, then NP
= RP
(Valiant–Vazirani theorem).
He is the brother of UC Berkeley computer science professor Umesh Vazirani
. In 2005 they both were inducted as Fellows of the Association for Computing Machinery
.
Vazirani
Vazirani is one of the rare surnames of a group of Hindu Sindhi Amils that have origins and roots in the Sindh province of Pakistan, especially around the Sukher region. Vaziranis are spread all over the world....
( ; b. 1957) is an Indian American
Indian American
Indian Americans are Americans whose ancestral roots lie in India. The U.S. Census Bureau popularized the term Asian Indian to avoid confusion with Indigenous peoples of the Americas who are commonly referred to as American Indians.-The term: Indian:...
Professor of Computer Science at Georgia Tech
Georgia Institute of Technology
The Georgia Institute of Technology is a public research university in Atlanta, Georgia, in the United States...
.
He received his Bachelor's degree
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
from MIT in 1979 and his Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian Institute of Technology, New Delhi
New Delhi
New Delhi is the capital city of India. It serves as the centre of the Government of India and the Government of the National Capital Territory of Delhi. New Delhi is situated within the metropolis of Delhi. It is one of the nine districts of Delhi Union Territory. The total area of the city is...
. Vijay Vazirani was also a McKay Visiting Professor at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
.
Career
His research career has been centered around the design of algorithms, together with work on computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, and game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
.
During the 1980s, he made important contributions to the classical maximum matching problem. During the 1990s he worked mostly on approximation algorithms, championing the primal-dual schema, which he applied to problems arising in network design, facility location and web caching, and clustering. In July 2001 he published a book on approximation algorithms (Springer-Verlag, Berlin).
One of his significant research results was proving, along with Leslie Valiant
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
, that if UNIQUE-SAT is in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, then NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
= RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
(Valiant–Vazirani theorem).
He is the brother of UC Berkeley computer science professor Umesh Vazirani
Umesh Vazirani
Umesh Virkumar Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
. In 2005 they both were inducted as Fellows of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
.
External links
- "Vijay Vazirani", Georgia Tech School of Computer Science
- "Vijay V. Vazirani", Mathematics Genealogy Project