Workhop on Sparsity, Coding, and Complexity

Workshop on Coding, Complexity and Sparsity will be at Ann Arbor, Aug 1--4, 2011. It is organized by Anna Gilbert, S Muthukrishnan, Hung Ngo, Ely Porat, Atri Rudra, Martin Strauss. The basic premise is that there has been a lot of nice interaction between coding and complexity theories, and a fledgling interaction between sparse representation and coding theories; academic research will be far richer exploring more of the connections between sparse representation and coding theories, as well as, between sparse representation and complexity theories. Could there be a general structural complexity theory of sparse representation problems and could techniques from algorithmic coding theory help sparse representation problems?

Let us get researchers from different areas together in a dagstuhl-like setting and explore the question. There will be tutorials, talks and time to research. Anna and Martin lead local arrangements, Atri is quarterbacking the effort, and I am playing the data stream researcher, highlighting the role of both upper and lower bounds from data streams that apply to sparse approximation and coding problems.