Mathematics in Theoretical Computer Science: Some Illustrative Examples

Dr. William Gasarch

Department of Computer Science

University of Maryland, College Park

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:

- 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! - 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(
*n*) processors (in one round compare everything to everything). Can you do this in substantially less than^{2}*n*processors? Can graph theory and probability help? Come to the talk and find out!^{2} - 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)*n*possibilities. Can you do substantially better than^{17}*n*? Can the Graph Minor Theorem help? (the what?) Come to the talk and find out!^{17}

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.

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