During the 1980s, he made seminal contributions to the classical maximum matching problem,[3] and some key contributions to computational complexity theory, e.g., the isolation lemma, the Valiant-Vazirani theorem, and the equivalence between random generation and approximate counting.

[4] 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[5] and web caching, and clustering.

In July 2001 he published what is widely regarded as the definitive book on approximation algorithms (Springer-Verlag, Berlin).

Since 2002, he has been at the forefront of the effort to understand the computability of market equilibria, with an extensive body of work on the topic.

His research results also include proving, along with Leslie Valiant, that if UNIQUE-SAT is in P, then NP = RP (Valiant–Vazirani theorem), and obtaining in 1980, along with Silvio Micali, an algorithm for finding maximum matchings in general graphs; the latter is still the most efficient known algorithm for the problem.