Latest news from the unnamed-but-working-on-it theoryCS Q&A site

4 days in (public) beta, and the theoryCS Q&A site (or as someone described it, the 21st century Usenet) is chugging along. There are nearly 600 users now, with nearly 300 "active" users - people who've posted, asked a question, commented, etc. Since there isn't a way to broadcast to the user community directly, I'm taking the liberty of doing it here.

If you're enjoying using the site, please visit the meta site (click the small 'meta' on the top banner). If you don't like how the site is working, please visit the meta site. In both cases, you'll find important discussions about how the site is working and should work, and your input will shape how it evolves. For example,

• What's the appropriate level for questions on the site ?
• How should questions be tagged (for easy searching and indexing)
• Who should be moderating ? 
• Which questions should be closed (deactivated) if any ? 

and almost as important:

• What should the site name be ?

Another reminder: please use your votes liberally. In fact, if you think a question is worthy of being read, it probably deserves an upvote (and the same for an answer). Frequent voting makes the whole system run smoothly.

And now, back to your regularly scheduled theoryCS programming:  some interesting recent questions for your entertainment (please comment at the question links, rather than here):

• Are there good constructions of space-efficient expanders ? 
• Can you design a heap with a stable ExtractMin operation (without using time-tags)? 
• When is polynomial testing equivalent to polynomial evaluation ?

cstheory Q&A site now open to the public !

The theoryCS Q&A site, in private beta the last seven days, is now open to the public. Please visit, ask questions, answer them, and hopefully we can make this a valuable resource for the community. There are currently over 100 questions, 300 answer, and 300+ users ! Some of the questions that I thought were quite interesting:

• Analogs of compressed sensing
• The importance of Integrality Gap
• Surprising Results in Complexity
• How hard is unshuffling a string (now with a bounty!)
  

If you have questions about the site and the protocols for questions, please visit the meta site. There, a bunch of users are trying to flesh out what will be the policies, as well as elect temporary moderators, and so on.

cstheory q&a site now open !

After a long wait, the theoryCS q&a site is now open. It's in private beta for the next 7 days, so if you didn't commit already, you'll have to wait till next Monday.

Please visit the site, ask your questions, and answer other questions. Some points to note from experience with Mathoverflow:

• If you're so inclined, please participate in the meta site as well. That's the place for discussions about the site itself, and is a good place to get involved and help shape the community.
• Please vote liberally and often. Especially in the beginning, voting questions and answers up when appropriate helps encourage others to stick around and participate more. If a question seems interesting enough to read, it deserves an upvote !

Social theoryCS...now 98% better...

Whatever you may think of the P vs NP hullabaloo over the past week, it has to be said that as a social experiment in peer review, this was an exhilarating and magnificent process to watch. There's enough chatter in the media about how this might point the way forward for peer review, and I'm skeptical of drawing too many conclusions from this one experiment with arguably the most important problem in our field.

But I'm encouraged by both the level of participation, and the enthusiasm it has generated about the field. I can't troll through the over 800 comments to find them, but I read numerous comments about how watching this process unfold made the commenter ever more excited about getting into theoryCS. Bob Sloan made a brief cameo to point out the value of this discussion as an outreach tool.

This is a long way of coming around to the news that the theoryCS Q&A site is now at 98% commitment, which means that some time in the next few days it'll go into beta. The beta stage starts with a 'private' seven day period, in which only those who committed (and therefore have promised to answer/ask a total of 10 questions over the entire beta duration of 90 days) get to use the site. After that seven day period, the doors will open for any interested participants.

The initial seven day period will have strong administrative elements (seeding the site with questions, discussing meta issues about the scope of questions etc), and while no major issues will be resolved, you can have some influence about how the forum gets shaped if you get in early. So if you haven't committed yet, do so, otherwise you'll have to wait the 7 days to get in.

P vs NP: What I've learnt so far...

(ed: note. it is somewhat embarrassing to be categorized as someone "trying to unravel what is up with the claimed proof". All I've really helped with is getting the wiki set up, and I'm very impressed with the amount of work that everyone is putting into keeping it current)

Whether or not Deolalikar's proof turns out to work, I have to say that in a span of three days, I've learnt a heck of a lot about the individual components in his paper.

• Like everyone else, I learnt my descriptive complexity back in the day, and marvelled at the fact that P, NP and PSPACE could be characterized syntactically. The discussions about the subtleties of the order relation in LFP have been fascinating though, and while the issue remains unresolved, there's a wealth of new(er) material that I've now been exposed to. 
• Similarly, while I was familiar with the idea that hardness could be captured as a phase transition in random k-SAT, the bizarreness of the landscape (clustering! freezing! condensation!) was quite new to me, and it's been illuminating to learn from the experts.
• The relationship between the solution space for k-SAT and error-correcting codes is also something that I was not aware of. And it might be the source of yet another issue with the paper. 
• A point made by Terry Tao is even more intriguing:
  
  

  If nothing else, this whole experience has highlighted a “philosophical” barrier to P != NP which is distinct from the three “hard” barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “global”) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)

There's been a bit of back-and-forth on whether "too much time" is being spent on perusing this paper, and of course people are entitled to their own opinions on this matter.

My take is slightly different. While none of the "revelations" listed above are new to people in the relevant areas, they're certainly new to me, and given how unlikely it is that I'd be able to pigeon-hole the relevant experts one-on-one to explain these ideas to me, the discussion is serving an important purpose. In effect, it has created a virtual workshop with even more discussion than a real one !

We've spent a lot of time over the past few years bemoaning the fragmentation of theoretical computer science, and have spent many blog-hours arguing over how to make STOC a destination conference for theoreticians again. But what the discussion over this paper has done is bring together experts in very different areas to talk with each other and exchange ideas, results and the crucial "mental frameworks" that are usually impossible to share except in oral discussions.

And that, in my view, is a net plus regardless of what happens with the proof.

A 'polymath' home for analysis of the Deolalikar proof

In collaboration with the Polymath project (and many thanks to Terry Tao for making this happen, and putting in lots of editing work in short order), there's now a new wiki to collect various threads of the discussion on the Deolalikar P != NP paper (which has been updated). With a lot of help from Terry, I've seeded the wiki with the initial discussion points that have come up. Please continue to edit this page as new ideas come up, or there's other discussion of the paper. 



This wiki replaces the Google doc that I had originally set up: it's a lot easier to edit, and Google was struggling under the weight of all the people trying to view the file.

The Lipton/Regan posts will continue to host the main research threads. If you are so inclined, you can use this post for "meta"-discussions as is customary in polymath land. Content will be transferred over to the wiki periodically, and more discussion threads can be forked if things start getting unwieldy (the first Lipton post is pushing 117 comments already).

On the Deolalikar proof: Crowdsourcing the discussion ?

 Update: the google doc has been replaced by a wiki. Please read this post.

By now everyone knows about the new proposed proof that P $\ne$ NP by Vinay Deolalikar. Better minds than mine are on the case right now, and little snippets of questions are coming out in comments (especially on Dick Lipton's original post).

It's a little hard to keep track of all the discussions, so I thought I'd try a crowd-sourcing experiment. At this link is a google doc that contains some of the initial discussion topics being raised around the proof. It's crudely organized, with a section for each major set of issues, and paragraphs for each person's comment, with sourcing via URL.

It's editable, so here's the idea. As you see issues get raised and resolved, enter that into the doc. The following rules apply:

• No discussions: this should be comment/resolution only ! 
• No personal, or nontechnical commentary. This is purely for discussion of the mathematics involved, and nothing else
• Add references (urls, or whatever) whenever possible, and quote all context so as not to cause miscommunication.

The goal is to collect the discussions in one place. Ideally, this would be some kind of polymath setup, and maybe it can be converted over to that (if someone does set it up that way, I'll add a link here).

Let's see if this works !