Here are some research topics I am interested in and have studied to varying degrees. I included online introductions to some areas and intend to incorporate additional outlines later on.
Communication
I am mostly interested in concrete (non-asymptotic, zero-error) communication scenarios. The issues underlying these topics are typically combinatorial or algorithmic. Here are three examples.
-
Interactive communication
In many applications a sender wants to convey information
to a receiver who has related data.
For example, a meteorologist may want to convey the temperature in
New York to a colleague who knows the temperature in New Jersey.
A reporter may wish to communicate today's stock prices to the
editor who has yesterday's closings.
Or a web page may need to be transmitted from a site to a user who
stores an earlier version of the page.
Interactive communication asks how many bits must be transmitted, and whether that number can be reduced if the communicators are allowed to interact.
The following outlines describe some of the issues involved.
- General overview: Introduces interactive communication via examples and presents basic results on the savings afforded by interaction, showing for instance that one message may be exponentially wasteful, but just two messages suffice for near optimal communication.
- Balanced distributions: Considers communication problems where the sender and receiver possess "comparable" data (like two related files) and shows that for all these problems information can be communicated almost as efficiently as if the sender had known the receiver's data in advance.
- Average-case analysis (coming "soon"): Shows among other results that for the average number of bits interaction can yield arbitrary savings and that four messages are asymptotically optimal.
-
Communication complexity
How many bits must two communicators exchange to determine if their
versions of a file are identical?
or two seismic stations to determine the location of an earthquake?
or, more generally, two computers to determine some function of their
combined data?
These are the questions addressed by communication complexity.
- Repeated communication Consider any communication problem. Do k independent instances require k times as many bits? No. For some problems, multiple instances, even though completely independent, require about as many bits as just one instance.
Speech processing
Speech recognition is of both practical and theoretical interest. Along with several students we are looking at information theoretic approaches to speech processing. Some of the issues involved are:- Recognition
- Compression
- Synthesis
Data Compression
- Vector quantization
Learning
- On line learning
- Investment theory
