STOC 2014 announcement.

Howard Karloff writes in to remind everyone that the STOC 2014 early registration deadline is coming up soon (Apr 30 !). Please make sure to register early and often (ok maybe not the last part). There will be tutorials ! workshops ! posters ! papers ! and an off-off-Broadway production of Let It Go, a tragicomic musical about Dick Lipton's doomed effort to stop working on proving P = NP.

At least a constant fraction of the above statements are true.

And if you are still unconvinced, here's a picture of Columbia University, where the workshops and tutorials will take place:

FSTTCS in December

At this point, you're probably wondering: exactly how much more coffee do I need to infuse into my system to get my 1/3/10  papers submitted to SODA before the deadline ? Do your stomach lining (and your adenosine receptors) a favor and consider submitting to FSTTCS: the abstracts deadline is Jul 8, and the submission deadline is July 15. You get to go to Guwahati in December and you might even get to stay here:

SODA 2014 abstract submission deadline approaching

+Chandra Chekuri informs us that the abstract submission deadline for SODA 2014 is approaching rapidly. Abstracts MUST be in by July 3 or else you cannot submit a full paper (by Jul 8).

For more information, visit the SODA site: http://siam.org/meetings/da14/submissions.php

Coding, Complexity and Sparsity 2013 (SPARC) 2013.

Atri Rudra reminds us that the 3rd incarnation of SPARC is soon to be upon us (disclaimer: I'll be speaking at the event):

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. 

The Coding, Complexity and Sparsity workshop (SPARC 13) will be held in Ann Arbor, MI on Aug 5-7. 

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. 

This is the third incarnation of the workshop and the previous two workshops were also held in Ann Arbor in August of 2011 and 2012. 

Confirmed speakers:

* Jin Yi Cai (University of Wisconsin, Madison)

* Shafi Goldwasser (MIT)

* Piotr Indyk (MIT)

* Swastik Kopparty (Rutgers University)

* Dick Lipton (Georgia Tech)

* Andrew McGregor (University of Massachusetts, Amherst)

* Raghu Meka (IAS)

* Jelani Nelson    (Harvard)

* Eric Price (MIT)

* Christopher Ré (University of Wisconsin, Madison)

* Shubhangi Saraf (Rutgers University)

* Suresh Venkatasubramanian (University of Utah)

* David Woodruff (IBM)

* Mary Wootters    (Michigan)

* Shuheng Zhou (Michigan)

We have some funding for graduate students and postdocs with preference given to those who will be presenting posters. For registration and other details, please look at the workshop webpage: http://eecs.umich.edu/eecs/SPARC2013/

Workshop on coding theory, complexity and sparsity

Atri Rudra asks me to post an announcement for the second incarnation of the workshop on coding theory, complexity and sparsity. The first event went off quite well - I was sure that Dick Lipton had a post on it but I couldn't find it (Update: here it is, thanks to Atri). At any rate, do attend and get your students to attend: they have a great roster of speakers and travel support for students.

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.

Confirmed speakers:

• 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: https://sites.google.com/site/umccsworkshop2012/

Workshop on Parallelism, and a "breakthrough" in combinatorial geometry

In the blog world, you're either fast, or dead. I waited a few days to post a note about the upcoming DIMACS workshop on parallelism, and was beaten to the punch by Muthu and Dick Lipton.

At this point, you probably know the major points. Phil Gibbons, Howard Karloff and Sergei Vassilvitskii are organizing a DIMACS workshop on a long-range vision for parallelism, with an emphasis on interaction between practitioners and theoreticians in the area. The workshop looks to be quite interesting, and similar in spirit to the one organized by Uzi Vishkin at STOC 2009 on multicore algorithms.

Utah has a major presence in the world of high performance parallel computing, and we're hiring in this area this year ! From my vantage point, I get a fly-on-the-wall view of developments in the area, and it makes me wonder:

Is the field is now moving too fast for models to even make sense ? 

A case in point: Google's MapReduce infrastructure has taken the world by storm, and you can even run MapReduce "in the cloud" on Amazon's servers. Howard, Sergei and Sid Suri had a very interesting paper on MapReduce at SODA last year, and there's a ton of academic work on algorithm design (in theory and practice) in this model. But if new reports are to be taken seriously, Google itself is moving on from MapReduce to other distributed data management systems.

The most recent "alternative model of computing" that we've encountered is the stream model, and while it had strong links to practice, it's survived this long because of the incredibly interesting theoretical challenges it poses, as well as the rich arsenal of theory concepts that got deployed in the process. I'm curious to see if something similar can happen with these new models of parallelism and multicore computing (over and above PRAM and NC of course)

In other news: readers of Gil Kalai's blog will have heard of the exciting new breakthrough in the realm of combinatorial geometry on the tantalizingly simple problem first posed by Erdos in 1946:

What is the minimum number of distinct distances achievable by a set of n points in the plane ? 

I hope to have a longer guest post up soon on this, so I won't say much right now. What's neat is that this result is the implementation of a larger program/line of attack laid out by Gyorgy Elekes, who sadly died in 2008 before seeing this come to fruition. Micha Sharir has a beautiful writeup with the history of this approach (it predates the new results though). Bill Gasarch has a nice page collecting together the major developments in this area, including links to the Kakeya problem.

p.s Note to other CG bloggers: please do not talk about this problem otherwise Mihai will scold us all ;)