Modern applications of computer science ultimately
depend on having highly efficient algorithms for solving
basic computational tasks; some examples are searching
and summarizing a large corpus of textual data, finding
optimal routes in networks, or finding an optimal
solution to a set of linear inequalities. Efficiency is a fine goal, but what is it exactly? We try to characterize, in a
mathematically rigorous way, the computational resources
(running time, storage space, communication, energy, etc.)
required to solve various combinatorial and optimization
problems. We also investigate how changing the model
of computation affects the complexity of solving specific
problems. For example, we now know that quantum
computers could solve some problems exponentially
faster than a classical computer and that many other, but
not all, problems can be solved significantly faster on a
Algorithms research at Michigan spans across many areas, including network optimization, approximation algorithms, the design and analysis of data structures, combinatorial problems in geometry, analysis of social networks, and algorithms for various parallel, distributed, and streaming models of computation.
Compton, Kevin J.
Stout, Quentin F.
Strauss, Martin J.
Related Labs, Centers, and Groups
Software Systems Laboratory