Alon Orlitsky: research

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.


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


  • On line learning
  • Investment theory