Research in combinatorial algorithms has a different flavor than that many other areas of computer science. It is inherently a game of posing and solving problems. Although the basic tools and paradigms of algorithm analysis are theoretical, this problem-solving approach lends itself naturally to applied problems.
I will illustrate these ideas with examples from some recent work. In particular, I will describe a system we built to permit single-stroke text entry on telephone keypads. The overloading of three letters on a single key creates an ambiguity as to which character was intended, which must be resolved for unambiguous text entry. By exploiting information theoretic constraints, we have developed algorithms capable of correctly identifying up to 99\% of the characters in typical English text, sufficient for such applications as telephones for the hearing-impaired, E-mail without a terminal, and advanced voice-response systems.
If time permits, I will also describe our current research in computational biology.