Author Archive

Consider the problem UNSHUFFLE:

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square. Is there a fast algorithm to determine whether a string is square, or is it NP-hard ?

Today is the one year anniversary of this problem, first posed by Jeff Erickson on cstheory  on August 16, 2010.

The problem received furious attention on the site, with a number of (sadly erroneous) solutions being proposed. One nontrivial observation was made by Per Austrin, who showed that the problem is easy (by reduction to 2-SAT) if each character occurs at most four times. This problem also spawned a paper by Henshall, Rampersad and Shallit that studies properties of shuffle languages.

There’s another anniversary today – of cstheory itself ! On August 16, 2010,  the cstheory stackexchange site came online. In the past year, we’ve racked up 2100+ questions and nearly 5000 users. We elected site moderators, and even started a dedicated blog (that you’re reading right now). We’ve had a number of original proofs produced on the site, and answers covering topics in complexity theory, algorithms and data structures, geometry, quantum computing, and so many more areas. We’re also beginning to see references to the site appear in papers.

It’s been a busy year.

A year on in, one could ask: do we need cstheory ? John Sidles provided one answer:

in the 21st century, mathematical genius is as scarce as ever, and yet fortunately, the ability to “prove what we want” is becoming ever-more-widely distributed. This is in consequence of the confluence of several factors, among which are the ever-increasing volume of mathematical literature, the ever-improving access and searchability of that literature, and the literature’s increasing emphasis upon naturality and universality. And yet, these gains in mathematical volume, access, naturality, and universality aren’t much good without the additional crucial ingredient of community … and here both cstheory and its sister site Mathoverflow have made a contribution that (to my mind) is absolutely essential and wonderful. Thus (for me), not the sole contribution of cstheory to mathematics, but also not the least important, is the sense of community that cstheory fosters, and the concomitant mathematical confidence that “yes, we can prove what we want”, which cstheory so ably helps distribute among many people (young researchers especially).

Community is important. It’s becoming impossible to keep track of all the results being published. It’s also hard (and time-consuming) to travel to conferences. So a place where you can have ‘in the corridor’ discussions across the globe is very valuable. I think it’s particularly neat that a Ph.D student working in quantum computing can ask a question about whether to publish a result and have Peter Shor (and many others) help him. In fact, there’s now an invaluable and growing body of theoryCS-specific career advice that combines the knowledge and experience of the community, and would be difficult to get any other way.

So what can we look forward to in the coming year ? There are still many researchers out there who either haven’t heard of the site, or are not quite sure what it can do for them. I hope (and your ideas are welcomed) that we can grow the cstheory community to encompass more of the theoretical CS community at large.

I’d like to see ways of integrating this site into other research forums like conferences and workshops. How that might be done is again a topic for discussion (meta question, anyone?). We were hoping to get a formal link between this site and SIGACT, but the powers that be at Stackexchange Inc. appears to have cooled on that idea for now.

But ultimately, we plan to be around for the second anniversary, and the third…

Our goal is to be the site every theoretican visits every day, and even more, the site that every theoretician feels COMPELLED to visit every day.

p.s An appeal: we’re looking for volunteers to write blog posts for the cstheory blog. Posts don’t necessarily have to be about the site: in fact, it might be neat to have conference reports posted here. If you don’t run your own blog (or do), and found yourself berating the theoryCS bloggers (that danged geomblog!) for not writing about your favorite topic, this is your chance ! If you’re interested, sign up by adding your name to this list.