This research project addresses fundamental challenges caused by imperfect or lacking synchronization in communications and information systems. Timing disparity, for example, between a sender and receiver pair or different components of a high-throughput processing unit may cause these errors. In such cases, the communicated symbols may be missed or registered multiple times by the receiver unit. In high-speed optical communications, data is encoded in the form of intensity variations of light beams. As photons travel through the communications medium, they may be absorbed or arrive at the destination in an unpredictable order. The photon detecting receiver will then need to translate the unreliable photon counts over time to the precise digital data being sent. More recently, reliable and extremely compact storage of massive digital data in DNA molecules has been an active subject of study. In such applications, the stored information is retrieved via existing DNA sequencing technologies that are also prone to synchronization errors. The scientific impacts of the project span the above-mentioned technologies that are of key significance to the processing, transmission, and storage of massive data. Educational aspects of the project include training postgraduate and undergraduate students and incorporating elements of the project into coursework.
The above examples divide the specific goals of the project into three main categories. First, Shannon capacity of the deletion channel, as well as related communications channels, will be studied. A main goal will be to obtain provable and improved bounds on the information capacity. Second, Shannon capacity of the Poisson channel, a classical model for optical communications, will be studied. The project sets forth the novel hypothesis that the deletion and Poisson capacity problems, two of the longest-standing open problems in classical information theory since the 1960s, have remained unresolved due to shared mathematical difficulties, and thus should be studied with a shared perspective. Finally, the project studies the complexity of the trace reconstruction problem which provides a mathematical model to study the capacity of DNA storage systems.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
