Mihalis Yannakakis | Calculating What Is Possible

Mihalis Yannakakis
Percy K. and Vida L. W. Hudson Professor of Computer Science and Professor of Industrial Engineering and Operations Research
This profile is included in the publication Excellentia, which features current research of Columbia Engineering faculty members.
                               Photo by Eileen Barroso

Computers are solving ever more complex problems, yet some problems have resisted intense efforts for many decades. How can we tell which problems can be solved efficiently and which cannot? How do we find the most efficient algorithms? And for intractable problems, how do we find the best solutions possible in reasonable amounts of time? These are some of the challenges taken on by Mihalis Yannakakis.

One line of his research seeks to understand the inherent computational complexity of problems.

“It turns out that many computational problems from diverse fields are intimately related to one another,” he said.

For example, optimizing network designs, scheduling jobs, and folding proteins all exhibit essentially the same type of computational difficulties. Yannakakis seeks to find the underlying features that characterize the complexity of different problems and identify their unifying principles.

Many optimization problems are computationally hard, in the sense that we cannot compute efficiently the optimal solution. For these cases, Yannakakis has been working on algorithms that compute near-optimal solutions. His goal is to design efficient approximation algorithms with provable performance guarantees.

Yannakakis’ third research thrust involves trade-offs when making decisions.

“We care about a design’s quality and also its cost, or a health treatment’s benefits and risks. Typically, there is no one solution that is optimal for all criteria, but rather many incomparable solutions that encapsulate the trade-offs between different criteria,” he explained.

For two criteria, Yannakakis visualizes these trade-offs as a curve on the plane. As the number of criteria rise, the trade-offs form a surface in a higher dimensional mathematical space.

“It is generally impossible to generate all the points on the trade-off surface because there are usually an exponential or even infinite number of them,” he said. “But we wish to generate enough points to represent the whole design space, so decision makers have an accurate enough view of the trade-offs to make an informed choice.”

Yannakakis’ approach is to design algorithms with guaranteed succinctness and accuracy to compute a carefully selected small set of solutions that offer the best possible representation of that space.

“Computers could work forever on a task,” he summarized. “We try to characterize what we can actually compute efficiently for a specific task and in general. Like trying to understand the physical world, we’re trying to find the laws that govern the computational world. We want to determine the powers and limitations of computation.”

Dipl., National Technical University of Athens (Greece), 1975; M.S., Princeton, 1979; Ph.D., Princeton, 1979

500 W. 120th St., Mudd 510, New York, NY 10027    212-854-2993