FXPAL Blog

Scott Aaronson has been asked by MIT to put together a list of the top 150 events in computer science history as part of the celebration of MIT’s 150th anniversary. You can vote on the potential entries here (you will need to register by providing a login name, password, and e-mail address). For more information about the project, see this blog post which includes an early version of the list, and a more recent blog post of his on the subject.

I’ve mentioned some of Scott’s work before, in a post about classical computer science results inspired by quantum information processing, and in a post on an overview of  quantum computing for technology managers I wrote a couple of years ago. His results don’t make it into the top 150 computer science results of all time, but are good candidates for a list of the top 150 results of the last decade.

Former FXPAL intern Jeremy Kubica’s Computational Fairy Tales is a fresh new entry into the blogosphere that introduces a unusual way to learn computer science: read a series of charming fairy tales. Each post contains a few sentences of introduction to a computer science concept followed by a fairy tale illustrating that concept.

I particularly enjoyed Loops and Making Horseshoes which illustrates (more…)

AT&T Bell Labs has recently made their entire archive of the Bell Systems Technical Journal (BSTJ) available for free on-line. The collection goes all the way back to 1922. In fact, the first issue has an article on the transmission characteristics of the submarine cable. For example, in 1978 an entire issue of the journal was dedicated to a new operating system called Unix.

(more…)

Ten days ago,  a theoretical computer science community Q&A site went beta and seems to be generating a fair amount of activity. I’m a big fan of MathOverflow, and am delighted to see a similar site springing up for a different field.

Thirty-nine days ago,  a new mathematics site went beta, which initially puzzled me since the mathematics community already has the highly successful MathOverflow site. The difference appears to be that MathOverflow is specifically for research mathematics whereas the new site aims to be broader, allowing more elementary questions.

Overall, I think a proliferation of such sites is great, but it is also confusing. It isn’t always clear when a question is research level or not. There are questions tagged algebra or topology on the CS theory site that are pure mathematics questions. There’s a question tagged  graph theory that had been posted previously to MathOverflow. I am delighted to see that both cs.cr.crypto-security and quantum computing already are populated with a few questions, but similar questions in these areas received good answers on MathOverflow. It would be a shame if the proliferation of sites lead to less interaction between fields rather than more. I’ll be curious to see how the usage patterns play out over time.

For those of us with a passing (or greater) interest in algorithms, last week was particularly interesting: Vinay Deolalikar circulated a paper that attempted to prove P≠NP. This is one of the great unsolved problems in Computer Science, and its solution has some important implications for real-world problems such as keeping your money in your bank account.

I won’t attempt a summary of the proof, and will limit myself to social commentary.

(more…)

Artificial intelligence has always struck me as a fittingly modest name, as I emphasize the artifice over the intelligence. Watson, a question-answering system has recently been playing Jeopardy against humans to test the “DeepQA hypothesis”:

The DeepQA hypothesis is that by complementing classic knowledge-based approaches with recent advances in NLP, Information Retrieval, and Machine Learning to interpret and reason over huge volumes of widely accessible naturally encoded knowledge (or “unstructured knowledge”) we can build effective and adaptable open-domain QA systems. While they may not be able to formally prove an answer is correct in purely logical terms, they can build confidence based on a combination of reasoning methods that operate directly on a combination of the raw natural language, automatically extracted entities, relations and available structured and semi-structured knowledge available from for example the Semantic Web.

As a researcher, I’m excited at the milestone this represents.

(more…)