Mathematics in Theoretical Computer Science: Some Illustrative Examples
Dr. William Gasarch
Department of Computer Science
University of Maryland, College Park
January 8, 2004
12:40 - 1:40pm
Bailey Hall 312
Abstract

Mathematics is used in many branches of theoretical computer science. This serves to motivate the mathematics and make it more interesting. We give three examples that illustrate this:

1. Communication Complexity. If Alice has x and Bob has y they want to see if x = y (both are of length 1000). One way to do this is to have Alice show Bob her entire string. This takes 1000 bits of communication. Can they do better? Can finite fields help? Come to the talk and find out!
2. Parallel Sorting. You have a list that you want sorted really really fast. In fact, we want it sorted in TWO steps. This sounds very hard; however, we will let you have many processors. So the problem now becomes- you want to sort in two rounds, how many processors do you need? You can easily do this in O(n2) processors (in one round compare everything to everything). Can you do this in substantially less than n2 processors? Can graph theory and probability help? Come to the talk and find out!
3. Gas Station Problem. There are n towns and highways connecting some of them. You want to place gas stations in towns such that every highway has one of its end points at a town with a gas station. You can only pick 17 towns. You could look at all (roughly) n17 possibilities. Can you do substantially better than n17? Can the Graph Minor Theorem help? (the what?) Come to the talk and find out!
Dr. Gasarch's visit is arranged in conjunction with the Department of Mathematics and with the help of the Center for Converging Technologies.

Lunch will be provided at 12:00 in Steinmetz 237, and a question session for students will follow the talk, also in Steinmetz 237.