Coding theory

This talk will be about a novel technique called spatial coupling originally invented for constructing better error correcting codes. One can use spatial coupling as a mathematical tool to derive properties of standard graphical models via an analysis of a coupled version. A general methodology for obtaining provable better (sometimes optimal) lower bounds for thresholds in coding theory and random constraint satisfaction problems will be outlined.

My talk will be a tutorial about sparse signal recovery but, more importantly, I will provide an overview of what the research problems are at the intersection of biological applications of group testing, streaming algorithms, sparse signal recovery, and coding theory. The talk should help set the stage for the rest of the workshop.

Group testing was formalized by Dorfman in his 1943 paper and was originally used in WW-II to identify soldiers with syphilis. The main insight in this application is that blood samples from different soldiers can be combined to check if at least one of soldiers in the pool has the disease. Since then group testing has found numerous applications in many areas such as (computational) biology, combinatorics and (theoretical) computer science.