A new theme song for Numb3rs ?

Kate Bush (remember her?) has a new album out. Called 'Aerial', it includes one song, 'Pi', that

is about a "sweet and gentle and sensitive man / With an obsessive nature and deep fascination / For numbers / And a complete infatuation with the calculation / Of Pi"

The song itself (and this is what caught my attention while driving into work listening to WXPN) is a recitation of the digits of pi, done so sonorously that if you weren't paying attention, you wouldn't even notice. Once you do though, you're amazed at how creatively one can say the numbers zero through nine without sounding monotonous. Here's a thought: instead of these annoyingly stilted voices that repeat numbers to you for confirmation when you call customer service, someone should break down the different ways Kate Bush sings each number and randomize them into a string that would sound so much more delightful.

You can send my royalties to my Paypal account at numb3rs@rules.com

Happy New Year !

Update: Michael links to an mp3 file.

Categories:

• numb3rs
• katebush

Diaconis lectures on the origins of probability

Persi Diaconis runs a course on the origins and philosophy of probability called 'Probability, Induction and Statistics'. It draws inspiration and content from Edwin Jaynes' book on probability, and lectures cover some of the profound philosophical debates that have raged through the ages on the meaning and interpretation of probability.

In algorithms, most of us use probability unthinkingly in what statisticians would call "a frequentist vein", where the probability of an event can be envisioned as the fraction of times it occurs on average over a large number of trials. The lectures in Diaconis' course (and indeed much of Jaynes' book) explain why even if you believe this view, it is not as simple as it seems, and how the Bayesian perspective (where probabilities can also represent strength of belief) is a consistent alternate view of the world.

Jaynes also pushed the idea that statistical mechanics can be reformulated via Bayesian reasoning methods; this was a powerful (and controversial) idea, and is too complex to discuss further here. If you're interested in reading more, you can start with Jaynes' papers here and here, and his summary of MaxEnt methods here.

---

Aside: I've started a QuickLinks section for links that might not necessarily merit a full post, but are interesting nonetheless. It's on the left side of the main page, and has its own RSS feed.

Categories

• probability
• diaconis
• jaynes

Computer science vs programming, II

I should add that the view presented in the Globe article I just mentioned is in direct opposition to an evolving perspective about the role of university computer science programs.

Namely, it is a view that university CS programs should be doing more towards helping students prepare for life in industry, like offering classes in various programming languages like Java, Python, and others, training students to write software, and generally addressing the needs of the computer industry.

Although I am strongly against the notion that such training merits a degree in "computer science", I see no reason why different schools might not take different tacks, offering different kinds of degree programs and specializing in different areas. What I do welcome is the idea that there is a pushback from the "computer science as a way of thinking" direction, as well as creative thinking about courses that might more effectively reflect this point of view (for more on this, see Siva's post about alternative courses, and Michael Mitzenmacher's comment at the same post)

Computer science vs programming

Via the CRA, an article that purports to be about the dwindling number of women computer scientists in the field, but is really about much more:

Some computer scientists fear that they may be going in the same direction. They view the dearth of women as symptomatic of a larger failure in their field, which has recently become less attractive to promising young men, as well. Women are ''the canaries in the mine," said Harvard computer science professor Barbara J. Grosz.

The article highlights geometer Diane Souvaine of Tufts, and her work in developing a curriculum that focuses more on the science than the computer in computer science. It makes a point that we in the field are all familiar with, but that I have never seen explained in the media:

Introductory classes zeroed in on programming and other technical aspects of the field, rather than explaining big ideas or talking about how computing can impact society, many professors say. That approach led to a misconception among students that computer science is the same thing as computer programming. Computer scientists say that view shortchanges the field, which is far broader and more intellectually rich. It is applied math and design, they say; it is about modeling human behavior and thinking about the simplest way to accomplish a complex task.

The other point the article makes that I really don't agree with is that a focus on programming and technical aspects of computers is what attracted male programmers (read "nerds") to the field, to the exclusion of females. The implication of course is that if computer science education were focused more on problem solving and "impact on society", that more women would have been inclined to enter the field.

This is debatable. Any higher level "non-programming-centric" approach to teaching computer science would involve heavy dollops of math; linear algebra, graph theory, calculus, probability, geometry, you name it, even if you never ended up doing theoryCS. Math has always had a problem attracting women students, and I don't see why shifting focus away from programming and towards problem solving (which I highly encourage, btw) would make the barrier to entry for women students any lower.

Physics, complexity and NP

Sometimes I feel like classical physicists must have felt when quantum mechanics first came marching through the door...

Lance Fortnow chats with Scott Aaronson about what physicists need to know about complexity, and Dave Bacon (almost)-snarks that maybe we should be asking what computer scientists need to know about complexity.

He is referring to quantum complexity of course, the premise being quantum computing represents the definitive description of all "efficient" computing devices, rather than a poly-time (or randomized poly-time) classical TM.

I'd like to think that all my years spent learning classical algorithms and complexity haven't gone to waste ;), but something Scott said on the podcast was very interesting. He argued that one should not expect that a QP algorithm will solve an NP-hard problem. Now I don't know if this is a view shared by the quantum computing community in general, but it's definitely something I didn't expect: I had always imagined that the odds were in favor rather than against BQP containing NP.

Categories:

• quantum
• computing

Great conference papers that never made it to a journal, part 327...

It's no secret that theory folk are somewhat allergic to journal papers, only publishing them to kowtow to the tenure gods, and even then grudgingly. On that note, I recently "discovered" that two (more) very influential papers that I was familiar with had never made it to a journal.

Both are by Andy Yao, their influence is staggering, and at least one of them was directly mentioned in his Turing Award citation:

1. Some complexity questions related to distributive computing: The paper that introduced the idea of communication complexity appeared in STOC 1979.
2. Lower bounds by probabilistic arguments: This paper introduced the idea of minimax reasoning for lower bounding randomized algorithms, and appeared only in FOCS 83.
   
   

---

Footnote: If you haven't seen it, it's "new to you" :).

More cartograms

As seen by many all over the blogosphere, here's a cartogram (use the right term, people !) of the countries of the world based on population.

Tags: cartogram, population

ahhhh: or why I became a computer scientist.

I will join in the collective sighs of relief at the completion of yet another deadline. I'd like to officially grumble about anonymous submission procedures, because one of the few pleasures of completing a paper is being able to brag about it afterwards :), and not everyone is as enlightened as the IACR.

Anyhoo, here's what I dispatched to the annual sausage convention. No pdf yet alas, because of paper release procedures and the like.

Lance had an interesting post about why he became a computer scientist: it appears that his story (and that of many in the comments) is of someone with a strong math background ending up in a math program and moving to a computer science program (one commenter even cites a complaint among math profs about losing their students to physics and CS). My story was slightly different: after reading Stephen Hawking's 'Brief History of Time' I was convinced that I wanted to be a physicist. My main interaction with computers was as a hacker, writing video games (in assembly code to boot) on my dinky ZX Spectrum.

But then I found a book in the library (actually it was the British Council Library in New Delhi, for any Delhiites among you all) that talked about Alan Turing and the Turing test. It was a short hop, skip and jump from there to Searle's Chinese Room argument, strong AI, and Godel's Theorem. AI was my hook into computer science, and remained my major interest up through graduation, although a complexity theory class by Somenath Biswas (and a thesis under his supervision) started drawing me away from the "fuzziness" of AI and into TCS itself. Through all of this, I remained untouched by the "math bug" (though I always enjoyed it), and for the last many years have been playing a desperate game of catchup !

From the point of view of training, I'd argue that a math degree is indispensable, and I fervently wish I had gone that route. My meanderings through AI did give me a more "romantic" notion of the field though, which is not necessarily a bad thing :)

More random mumblings

The "standard" ACM conference style file is one of the most god-awfully ugly designs I have ever seen. Those who know me know that I like to obsess over nice fonts, and the clunky square font stylings that I am often forced to use just depress me.

On the other hand, SIGGRAPH (the graphics SIG of ACM) has an excellent style file, which often shows up in computational geometry proceeedings. I guess it's no surprise that the graphics folks are more sensitive to the layout and presentation of a paper.

Obviously, these are subjective judgements. So judge for yourself:

• SIGGRAPH-style example PDF file.
• ACM Proceedings-style example PDF file. (this is the "alternate" style; the standard one has essentially the same look)
  

4 days and counting

If you're reading this, don't ! get those 10pt font submissions ready !