On 7/11/2011, I asked the question with the same name on the parent site. More precisely:

How important is knowing how to code in TCS (in fields where programming is not directly involved) : is there reasons which could bring a Computational Complexity theorist (for example) to know how to code? Is it worth spending a lot of time learning how to code? And if there are, is there a category (functional, imperative, object-oriented..) of programming language that would be more suited? I can imagine that someday I may have to implement some algorithms for my work, but then can I wait for this moment? Or is there something more?

I got so many good answers that I was advised to blog about it. This is my ‘grand debut’ so forgive me for my prose. I will not give every answers, only the part which I though were the most helpful to me. The rest of the answers can be found on the original question.

Reasons

1. Testing a Conjecture by Tsuyoshi Ito

Testing a conjecture with numerical calculation can save the time which would have been spent in vain trying to prove a false statement.

1.5 Visualization by John Moeller

A computer is a great tool, it allows you for instance to see in different dimensions that are hard to imagine. Being able to see stuff helps for new ideas.

2. Theoretical results are not always real results by Suresh Venkat

Some optimal algorithms could be really hard to implement, and then not usable in practice, maybe an algorithm not as efficient but that can be implemented would be a better result. It opens up new theoretical research direction.

3. Type-Checking your proofs by Alessandro Cosentino

Learning a functional language forces you to type-check your programs, which can be a big asset for later when you start to type-check your proofs. This statement was however shaded by Sasho Nikolov who stated that even though this was true, maybe it was not worth the time if this was the only reason to learn a functional language.

4. Teaching by Martin Berger

There is a chance that someday a researcher in a university will be given courses with a substantial programming component. Being already comfortable can help being a better teacher.

5. If you know you will need to learn someday, the sooner the better by Peter Shor

Otherwise when you will really need it you will not have time for it.

6. Programming can be fun by Tsuyoshi Ito

Comment +1’d by 11 people! That says it all I guess.

Languages

1. (Strongly-Typed) Functional

(+) Teach to type-check, useful for proofs.

(+) A must for the logic/PL semantics field.

(-) Time consuming

(-) Hard to “see” things (see argument for imperative language).

2. Object-Oriented

(+) easy to learn and implement simple algorithms

(+) A must for software engineers (modular re-usable code)

(-) If you do not want to re-use it, not necessary to go that far (see Imperative)

3. Imperative

(+) Get a feel of what’s fast and what’s slow

(+) A must for people interested in efficient algorithms and data structures

(+) Widely used, almost “everyone” has a C compiler (if you want people to use your implementation).

To conclude, I got a lot of interesting answers, answers I did not think of before, so i am really grateful. If you have more arguments pros or cons (there was not that many argument against learning to program when you do not directly need it), feel free to add them. I will probably learn to program in C thanks to this useful discussion (in case some wondered what my final decision was :)). I think it took over my phlegm.

Oh, and also, I learned that “Euclid was a very crappy programmer”.

Many CSTheory people probably know there is a new StackExchange Q&A site, Theoretical Physics, which is now in public beta, and was originally started by Joe Fitzsimons, co-editor of this blog.  My purpose for this post is to give TCS people a heads-up that there are now 16 questions on that site under the quantum-computing tag and the quantum-information tag that may be of interest to theoretical computer science.

My favorite of these questions is Rigorous Security Proof for Wiesner’s Quantum Money?  In this question, Scott Aaronson asks for an explicit upper bound on a value that is “known to exist” according to folklore, but that he and a co-author were unable to find in the literature or derive. Master’s student Abel Molina solves the problem, using a formalism of Gutoski and Watrous.  John Watrous then verifies the solution’s correctness.  There are also contributions by Dan Gottesman and Peter Shor.

In related news, there is now a proposal for a Quantum Information question and answer site on the Stack Exchange Area 51.  This proposal is (mildly) controversial, though, because some people are concerned it would duplicate topics already available on Theoretical Physics.

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.