DIMACS Seminar Series on Math and CS in Biology


Dialing for Documents: An Experiement in Information Theory


Steven Skiena
Department of Computer Science, SUNY Stony Brook


Room 431, CoRE Building,
Busch Campus, Rutgers University.


3:00 PM
Monday, January 30, 1995


Standard telephone keypads are labeled with letters of the alphabet, enabling users to enter textual data for a variety of possible applications. However, the overloading of three letters on a single key creates a potential ambiguity as to which character was intended, which must be resolved for unambiguous text entry. Existing systems all use pairs of keypresses to spell out single letters, but are extremely cumbersome and frustrating to use.

Instead, we propose single-stroke text entry on telephone keypads, with the ambiguity resolved by exploiting information-theoretic constraints. We develop 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.

A demonstration of the system will be given after the talk.

WARNING: This work is of no theoretical or biological interest. It is offered only to fill the seminar slot on short notice. I do think it is kinda neat, however.

This is joint work with Harald Rau.

Refreshments will be served at 2:45pm. If you need more information, please contact

Richa Agarwala (agarwala@dimacs.rutgers.edu) R. Ravi (rravi@dimacs.rutgers.edu) S. Muthukrishnan (muthu@dimacs.rutgers.edu) Vineet Bafna (bafna@dimacs.rutgers.edu)

Document last modified on January 27, 1995