Theme:Efficient and effective transmission, storage, and retrieval of information on a large-scale are among the core technical problems in the modern digital revolution. The massive volume of data necessitates the quest for mathematical and algorithmic methods for efficiently describing, summarizing, synthesizing, and, increasingly more critical, deciding when and how to discard data before storing or transmitting it. Such methods have been developed in two areas: coding theory, and sparse approximation (SA) (and its variants called compressive sensing (CS) and streaming algorithms).Coding theory and computational complexity are both well established fields that enjoy fruitful interactions with one another. On the other hand, while significant progress on the SA/CS problem has been made, much of that progress is concentrated on the feasibility of the problems, including a number of algorithmic innovations that leverage coding theory techniques, but a systematic computational complexity treatment of these problems is sorely lacking. The workshop organizers aim to develop a general computational theory of SA and CS (as well as related areas such as group testing) and its relationship to coding theory. This goal can be achieved only by bringing together researchers from a variety of areas. We will have several tutorial lectures that will be directed to graduate students and postdocs.Registration: If you are planning to attend the workshop, please register as soon as possible on the registration page. Registration is free and comes with many benefits such as a guest login to access the wireless network on campus. Also, it will help us estimate the number of people attending so that we may plan appropriately for refreshments during the lecture breaks.Registration deadline: July 15, 2011.
Registered ParticipantsLectures: (Please click on the title for more information including an abstract and suggested reading.)
A record of the lectures will be available after the conference.
Confirmed SpeakersYaniv Erlich
Dieter van Melkebeek
Virginia Vassilevska Williams
David WoodruffInstructional Tutorials:
These will be hour-long lectures designed to give students an introduction to the area.Brett Hemenway, Coding theory
Anna Gilbert, Compressive sensingParticipant support: We have limited support for participants (graduate students and postdocs) to attend. We will be able to cover only a portion of expenses (the standard NSF restrictions apply). To apply, please fill in the following information on the registration page.Name, University affiliation, Name of graduate advisor/ postdoctoral mentor, a very short description of your research interests, estimated roundtrip travel costs to Ann Arbor, and any travel support available from other sources; e.g., your home institution. In addition, if you are a graduate student, please request your advisor to send a short letter of recommendation to Anna Gilbert .Schedule and travel:
The local airport is Detroit, airport code DTW. There are taxis and shared ride vans available to Ann Arbor, which is about 25 miles from the airport.The workshop will begin on Monday, August 1 at 9 am and will end on Thursday, August 4 at 1 pm. Participants are expected to arrive on Sunday, July 31, and leave on Thursday, August 4, in the afternoon or evening. Depending on the arrival/departure schedule of a majority of the participants, we will schedule an afternoon off for a local recreational activity, in the style of a Dagstuhl workshop.Accommodation:
Blocks of rooms have been reserved at Holiday Inn North and Hampton Inn. (See Lodging)Useful links:
Airport transportation: Here are some links to shared van rides Ann Arbor Airport Shuttle, Custom Transit, Selectride,Michigan Flyer. Please note there are discounts for people traveling in groups. So participants arriving around the same time can save substantially by coordinating their ground transportation. Also taxis are available from DTW to Ann Arbor for a fixed rate of around $50 - $60.Local Transportation around Ann Arbor: from the University of Michigan Campus Information CenterMaps: Central Campus (Math Department is in East Hall)
Anna Gilbert, Martin Strauss, Atri Rudra,
Hung Ngo, Ely Porat, S. MuthukrishnanSponsors
Department of Mathematics, Institute for Mathematics and its
Applications (IMA), NSF, and Michigan Math Journal
In the meantime, the detailed program of SPARS11 is here.