January 8, 1999

Colloquium Topic: The Complexity of Problems

Given a Problem you want to solve, you want to know two things: 1) How well can I solve it (e.g., fast algorithm)? 2) Do I know I can¹t do any better? One view of theory is that its main focus is to take problems and find BOTH good algorithms, AND lower bounds on how good any algorithm could perform. The problem considered in this talk are: how hard is it to color an infinite graph? (are there analogs for finite graphs?) Is finding the maximum clique in a graph EASIER than finding a minimal route for a travelling salesperson? How fast can you find the kth largest of n elements? And several others. The talk is intended for a general audience.

---

Colloquium Speaker: William I. Gasarch

Professor William I. Gasarch received his Ph.D. in Computer Science from Harvard University in 1985 and joined the University of Maryland at College Park the same year. He became an associate professor in 1991 the very day that he got married (took years of planning!) and was promoted to a professor in 1998. His research interests include complexity theory, computability theory, and decision tree complexity. Professor Gasarch has written fundamental papers on, "Do more questions help one to compute more?," and on "Do more questions help one to learn more?" He has finished a monograph on the first topic. Professor Gasarch is an editor for Information and Computation, and Journal of Computers and Systems Science.