You are currently browsing the monthly archive for May 2012.
Atri Rudra asked me to post an announcement for this year’s
It’ll take place at the University of Michigan from July 30th to August 2nd. I really enjoyed last year’s workshop.
The Blurb. 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.
These will be hour-long lectures designed to give students an introduction to coding theory, complexity theory/pseudo-randomness, and compressive sensing/streaming algorithms.
We will have a poster session during the workshop and everyone is welcome to bring a poster but graduate students and postdocs are especially encouraged to give a poster presentation.
- Eric Allender, Rutgers
- Mark Braverman, Princeton
- Mahdi Cheraghchi, Carnegie Mellon University
- Anna Gal, The University of Texas at Austin
- Piotr Indyk, MIT
- Swastik Kopparty, Rutgers
- Dick Lipton, Georgia Tech
- Andrew McGregor, University of Massachusetts, Amherst
- Raghu Meka, IAS
- Eric Price, MIT
- Ronitt Rubinfeld MIT
- Shubhangi Saraf, IAS
- Chris Umans, Caltech
- David Woodruff, IBM
We have some funding for graduate students and postdocs. For registration and other details, please look at the workshop webpage:
While on the topic of STOC, I also wanted to mention a STOC workshop on “Algorithms for Distributed and Streaming Data” that will hopefully be of interest. It will take place Saturday afternoon, 19th May in NYU. The schedule can be found here.
So here’s the pitch: At this point it’s readily apparent that big data has become big news (e.g., see here and here). But what does this mean for the STOC/FOCS/SODA community? What are the algorithmic problems we could be solving? What are the appropriate computational models? Are there opportunities for industrial impact? What should we be teaching our undergraduate and graduate students? To address the relevant topics, we’ve lined-up a great set of speakers including Sergei Vassilvitskii, John Langford, Piotr Indyk, and Ashish Goel. Hope to see you there.
If yes, just a reminder that this year (for the first time) there’ll be an award for the best student presentation. More details here. In addition to the cash, the reputation for giving great talks can be very helpful when applying for jobs.
We’ll be giving preference to talks that are “clear, compelling, and appeal to a broad cross-section of the STOC audience.” My suggestion of giving extra credit for incorporating fire juggling, 3D slides, and celebrity guests fell on deaf ears.