- After CBS finished the pilot, they sent out letters to many mathematicians, asking for help in getting the math right (Ed was one of those who responded).

- They previewed the pilot at the 2005 Joint Math Meeting in Atlanta (the first TV pilot shown at a math conference!)
- They have mathematicians as advisors on the show.

Ruminations on computational geometry, algorithms, theoretical computer science and life

## Saturday, January 29, 2005

### Numb3rs and mathematicians.

Ed Pegg of Mathworld has a nice page describing some of the effort put in by CBS to achieve mathematical versimilitude on Numb3rs. Some of the salient points:

## Friday, January 28, 2005

### Numb3rs Review: "Pilot" and "Uncertainty"

I only just got around to watching the first two episodes of Numb3rs. My plan (for as long as I can stand it) is to record any mathematical nuggets of interest that are dropped in the show. Overall, the series is decent as a CSI-type action thriller. There is far more action than I had anticipated, which is probably a good thing: makes it more crowd-friendly.

I don't know if it will last very long: the acting is a bit uneven so far, and the writers have introduced plot lines that need to be explored further (the tension between Don and his boss; the (non)romance between Charlie and his "graduate student"...)

Peeve alert: Apparently this grad student is from Madras, and her parents are arranging her marriage with a Hindu banker from Goa. Just Hindu ? Not a Vadama Iyer brahmin of an appropriate gotram ? and from Goa, of all places ? They eat meat there, for crying out loud. In any case, who lives in Goa anyway ? I thought only foreign tourists live there.

So here's the setup. Don is the FBI agent, Charlie is his "math genius almost 30yrold brother" with degrees from MIT and Stanford (not Princeton ?). There are various other irrelevant characters like the Obligatory Female Sidekick (OFS), Token agent of color (TAC), and gruff but caring dad (GCD). I don't expect to mention them much. There is also the crazy string theorist/mentor for Charlie, who for some reason needs help with his math, and has to suffer cracks like "Feynman and Witten did their own math".

WARNING: there will be spoilers; don't read this if you have a problem with that.

1. Pilot:

Plot:

Main plot line revolves around determining from a set of points (locations of murders by a serial killer) the home base of the killer. Much rambling about sprinklers and how from the location of the drops one can reconstruct the location of a rotating sprinkler. The key dramatic element is familiar to anyone who knows clustering:

Mathematical jargon:

Not too bad overall. They even resisted the urge to claim that all mathematicians atrophy after age 30, merely having the mentor point out that Charlie was at the peak of his talents and most mathematicians have only 5-6 good years in them.

There was some good stuff about the difficult of humanly generating true randomness. and the usual bashing of the lottery (Don's boss makes fun of Charlie, but has a lottery ticket in his pocket). A useful mention of Galois (the mentor was worried that Charlie was getting distracted by "unclean" human problems).

One of the writers on the show has been reading blogs. There was a line that looked like it came from Sean Carroll's Preposterous Universe: "Why do we remember the past and not the future"

Charlie allegedly "built a weak force theory" with less than 96% probabillty. Whatever that means...

2. Uncertainty:

If there was any doubt in your mind that you should watch this series, this episode should dispel all of that. This, my friends, is the famous P vs NP episode (earlier than episode 4!)

Plot: Charlie has a new equation that predicts, given a series of bank robberies, where the next one will be. When the episode opens, he is being rather cocky about it. As it turns out he is right about the next location, but the standoff ends in a bloodbath and Don is injured, shocking Charlie so much he goes into a deep depression. As it turns out, the robbers are after something more involved.

Mathematical jargon:

The first inkling of what is to come appears after Charlie returns home, shell-shocked after seeing his brother wounded. He assembles blackboards like a madman in the garage, and as he walks by one board, you see the magic words: "SUBSET SUM". A few minutes later, you see another board covered with VERTEX COVER and COLORING and CLIQUE, with lines connecting them.

Be still, my beating heart....

Mentor dude walks in, and Charlie first states a theorem (the first of the series):

By the end of the episode all are happy and Charlie has realized that instead of working on P vs NP, he will work on problems that he has some hope of solving. Now there's a lesson for researchers everywhere !

What warmed the cockles of my heart was the constant referring to P vs NP as a "famous math problem". Now I would have been a little happier if this had been referred to as a "famous computer science problem", but the thought of "pure" mathematicians everywhere being driven crazy by this statement is good enough for me :)

Tags: numb3rs, review

I don't know if it will last very long: the acting is a bit uneven so far, and the writers have introduced plot lines that need to be explored further (the tension between Don and his boss; the (non)romance between Charlie and his "graduate student"...)

Peeve alert: Apparently this grad student is from Madras, and her parents are arranging her marriage with a Hindu banker from Goa. Just Hindu ? Not a Vadama Iyer brahmin of an appropriate gotram ? and from Goa, of all places ? They eat meat there, for crying out loud. In any case, who lives in Goa anyway ? I thought only foreign tourists live there.

So here's the setup. Don is the FBI agent, Charlie is his "math genius almost 30yrold brother" with degrees from MIT and Stanford (not Princeton ?). There are various other irrelevant characters like the Obligatory Female Sidekick (OFS), Token agent of color (TAC), and gruff but caring dad (GCD). I don't expect to mention them much. There is also the crazy string theorist/mentor for Charlie, who for some reason needs help with his math, and has to suffer cracks like "Feynman and Witten did their own math".

WARNING: there will be spoilers; don't read this if you have a problem with that.

1. Pilot:

Plot:

Main plot line revolves around determining from a set of points (locations of murders by a serial killer) the home base of the killer. Much rambling about sprinklers and how from the location of the drops one can reconstruct the location of a rotating sprinkler. The key dramatic element is familiar to anyone who knows clustering:

Make sure you know what the "right" number of cluster centers is !!!Short story: they thought the killer had one base, but he actually had two.

Mathematical jargon:

Not too bad overall. They even resisted the urge to claim that all mathematicians atrophy after age 30, merely having the mentor point out that Charlie was at the peak of his talents and most mathematicians have only 5-6 good years in them.

There was some good stuff about the difficult of humanly generating true randomness. and the usual bashing of the lottery (Don's boss makes fun of Charlie, but has a lottery ticket in his pocket). A useful mention of Galois (the mentor was worried that Charlie was getting distracted by "unclean" human problems).

One of the writers on the show has been reading blogs. There was a line that looked like it came from Sean Carroll's Preposterous Universe: "Why do we remember the past and not the future"

Charlie allegedly "built a weak force theory" with less than 96% probabillty. Whatever that means...

2. Uncertainty:

If there was any doubt in your mind that you should watch this series, this episode should dispel all of that. This, my friends, is the famous P vs NP episode (earlier than episode 4!)

Plot: Charlie has a new equation that predicts, given a series of bank robberies, where the next one will be. When the episode opens, he is being rather cocky about it. As it turns out he is right about the next location, but the standoff ends in a bloodbath and Don is injured, shocking Charlie so much he goes into a deep depression. As it turns out, the robbers are after something more involved.

Mathematical jargon:

The first inkling of what is to come appears after Charlie returns home, shell-shocked after seeing his brother wounded. He assembles blackboards like a madman in the garage, and as he walks by one board, you see the magic words: "SUBSET SUM". A few minutes later, you see another board covered with VERTEX COVER and COLORING and CLIQUE, with lines connecting them.

Be still, my beating heart....

Mentor dude walks in, and Charlie first states a theorem (the first of the series):

Minesweeper consistency is NP-Complete.and then mumbles something about 3SAT and coloring algorithms. Finally Don arrives, and the mystery is solved. It turns out that Charlie works on P vs NP whenever he's depressed. As OFS puts it: 'beats binge drinking and strip clubs'. Charlie is apparently so obsessed with this that when his mother was dying of cancer he spent the entire time working on it.

By the end of the episode all are happy and Charlie has realized that instead of working on P vs NP, he will work on problems that he has some hope of solving. Now there's a lesson for researchers everywhere !

What warmed the cockles of my heart was the constant referring to P vs NP as a "famous math problem". Now I would have been a little happier if this had been referred to as a "famous computer science problem", but the thought of "pure" mathematicians everywhere being driven crazy by this statement is good enough for me :)

Tags: numb3rs, review

### Looking out for number one

Most of us are familiar with "Zipfian distributions" or "heavy-tailed" distributions, in which the probability of occurrence of the i

A related "law" is Benford's law, which states that

Some other related laws that are more amusing, if less mathematically interesting are:

^{th}most frequent element is roughly proportional to 1/i^{a}, where a is a constant close to 1.A related "law" is Benford's law, which states that

On a wide variety of statistical data, the first digit is d with the probability logAn interesting discussion of this law reveals some underlying structure, specifically that if there is any law governing digit distributions, then it is scale invariant iff it is given by Benford's law._{10}( 1 + 1/d)

Some other related laws that are more amusing, if less mathematically interesting are:

Lotka's Law:

The number of authors making n contributions is about 1/n^{a}of those making one contribution, where a is often nearly 2

Bradford's Law:

Journals in a field can be divided into three parts, each with about one-third of all articles: 1) a core of a few journals, 2) a second zone, with more journals, and 3) a third zone, with the bulk of journals. The number of journals is 1:n:n^{2}

^{}### Shameless self-promotion

as of today, I now have over 100,000 page views (starting from Mar 31). Phew....

## Thursday, January 27, 2005

### Ah... coffee

The National Geographic Magazine has a spread on coffee, "the world's most popular psychoactive drug". Be sure to check out the multimedia tour of coffee organized by photographer Bob Sacha.

And do the quiz. You'll be surprised at some of the answers.

Courtesy Karen Ho.

And do the quiz. You'll be surprised at some of the answers.

Courtesy Karen Ho.

### More visa fiascos

You just can't win: when a conference is in the US, people have a hard time getting into the country, and when it isn't, people have a hard time getting back into the country.

At least one SODA PC member had visa trouble precluding their coming to Vancouver. Moreover, one of the Best Student Paper awardees (Ravikrishna Kolluri) couldn't make it for visa issues: someone else had to give the talk in his place.

At least one SODA PC member had visa trouble precluding their coming to Vancouver. Moreover, one of the Best Student Paper awardees (Ravikrishna Kolluri) couldn't make it for visa issues: someone else had to give the talk in his place.

### The fundamental silliness of all of this...

It's nice to have outsiders peep into our cloistered theory community from time to time. At dinner, I was trying to explain some of the business meeting discussion to John Baez, and the increasingly obvious look of incredulity on his face and my ever-more-convoluted attempts to explain myself soon made it apparent that something was seriously wrong.

Pretty much all of the annual handwringing we do over short/long/submissions/acceptance /quality/reviews/PC load and what have you, would just disappear in a "publish in journal/talk in conference" model. I realize that this is far too radical (though not innovative) an idea to ever be implemented any time soon, but you have to wonder why we in algorithms (and in computer science in general) put ourselves through such misery for no good reason. I have yet to hear a convincing reason why our model is superior to the math model

Admittedly our business meetings would be a lot shorter (not to mention less beer), but I am willing to pay this price :)

1The only reason I have heard is that our journals take too long to publish papers, but that assumes that this would not change if we had no conference reviewing.

Pretty much all of the annual handwringing we do over short/long/submissions/acceptance /quality/reviews/PC load and what have you, would just disappear in a "publish in journal/talk in conference" model. I realize that this is far too radical (though not innovative) an idea to ever be implemented any time soon, but you have to wonder why we in algorithms (and in computer science in general) put ourselves through such misery for no good reason. I have yet to hear a convincing reason why our model is superior to the math model

^{1}.Admittedly our business meetings would be a lot shorter (not to mention less beer), but I am willing to pay this price :)

1The only reason I have heard is that our journals take too long to publish papers, but that assumes that this would not change if we had no conference reviewing.

### SODA business meeting redux.

Adam Buchsbaum now has slides for his SODA 2005 business meeting presentation. After opening remarks and some basic statistics, he looked at acceptance rates across topics, and found that overall there is no advantage to be gained by focusing on specific areas. He thankfully skipped the now de rigeur "silly" section of the business meeting, where exotic formulae and elaborate paper titles that optimize acceptance are proposed.

The next section discussed diversity on the PC and in accepted papers, recapping the statistics that I talked about earlier.

Why Are Submissions Going Up ?

Next, he addressed what is a growing concern: increased submission levels and how to deal with them (this has become a serious enough problem that the ACM has a task force investigating the matter). His data comprises submission/acceptance information from 1999 forward (although for 1999 he only had long paper submission/acceptance rates). The most striking fact is the steady increase in submissions over the past 4 years. Note that this is not accounted for by the start of short paper submissions in 1999; current submissions levels are well beyond that.

Most of the increase can be attributed to an increased number of long submissions (but this will be addressed below). The main takeaway from this graph and from the subsequent plots is that the popular hypothesis "submission increases can be explained by the dot-com bust and lots of people returning to academia", is not supported by the data. The increase in new authors (as defined as people who had not submitted before year X) is steady, but not bursty. In fact the increase in paper submissions can be directly attributed to an increase in submitting authors, an increase that comes from both new authors and returning authors. Interestingly, drop-outs (people who never submit after year X) match returning authors quite well.

It does not appear to be the case that people are submitting more; weighted (by number of authors) and normal "papers/author" shows a small increase, but not significant.

Short vs Long

The next part of the presentation is where things get really interesting. Two charts display statistics on the scores of papers. The first one indicates the expected bell-curve like chart. The second chart (suggested by Piotr Indyk) plots score against reverse rank, and shows that except at the top 10% and at the bottom 10% of papers, there is no natural cutoff where an acceptance-rejection line can be drawn. This is significant, because often acceptance rates are claimed to be set by some "natural cutoff": for SODA this year, this appears not to be the case.

What all of this feeds into is a serious debunking of the value of short papers. Adam takes all the reasons that have been proposed for having short papers in the first place, and trashes them one by one:

1) Short papers increase acceptance of discrete math papers

BEEP ! This is not the case. Papers labelled as "discrete math" (which also includes CS papers with a strong discrete math component) in fact were accepted at a higher rate (34.5%) than the overal rate (27%). They also broke down into long and short submission rates the same way as non-DM papers.

2) Short papers provide an anchor for page lengths not at 12 (so that authors don't feel that their 6 page submission is viewed as inferior to a 12 page submission)

PZZT ! Wrong answer. Acceptance rates were not correlated with paper length. In fact many good 7-10 page papers were accepted. Compounding this was the fact that many short submissions had 7 pages of appendices (!).

3) Short papers allow for nascent and inter-disciplinary work.

This is a noble idea, but since we have reached the limit (135) of papers we can accept, any such short paper has to compete directly against a long paper, and invariably loses out. Basically, it is a zero-sum game at this point.

There was much wailing and gnashing of teeth at this point, but IMHO Adam's rather convincing presentation of the data quelled much discussion. After all, it's hard to have a strong opinion when there is clear data that contradicts it.

Will short papers die ? It's not clear. After one of the over 10 billion straw votes that we had, it was decided that the SODA 2006 PC would "take into consideration" the sense of the community, which was:

a) No extra tracks

b) Short papers MUST DIE (err... have problems).

The next section discussed diversity on the PC and in accepted papers, recapping the statistics that I talked about earlier.

Why Are Submissions Going Up ?

Next, he addressed what is a growing concern: increased submission levels and how to deal with them (this has become a serious enough problem that the ACM has a task force investigating the matter). His data comprises submission/acceptance information from 1999 forward (although for 1999 he only had long paper submission/acceptance rates). The most striking fact is the steady increase in submissions over the past 4 years. Note that this is not accounted for by the start of short paper submissions in 1999; current submissions levels are well beyond that.

Most of the increase can be attributed to an increased number of long submissions (but this will be addressed below). The main takeaway from this graph and from the subsequent plots is that the popular hypothesis "submission increases can be explained by the dot-com bust and lots of people returning to academia", is not supported by the data. The increase in new authors (as defined as people who had not submitted before year X) is steady, but not bursty. In fact the increase in paper submissions can be directly attributed to an increase in submitting authors, an increase that comes from both new authors and returning authors. Interestingly, drop-outs (people who never submit after year X) match returning authors quite well.

It does not appear to be the case that people are submitting more; weighted (by number of authors) and normal "papers/author" shows a small increase, but not significant.

Short vs Long

The next part of the presentation is where things get really interesting. Two charts display statistics on the scores of papers. The first one indicates the expected bell-curve like chart. The second chart (suggested by Piotr Indyk) plots score against reverse rank, and shows that except at the top 10% and at the bottom 10% of papers, there is no natural cutoff where an acceptance-rejection line can be drawn. This is significant, because often acceptance rates are claimed to be set by some "natural cutoff": for SODA this year, this appears not to be the case.

What all of this feeds into is a serious debunking of the value of short papers. Adam takes all the reasons that have been proposed for having short papers in the first place, and trashes them one by one:

1) Short papers increase acceptance of discrete math papers

BEEP ! This is not the case. Papers labelled as "discrete math" (which also includes CS papers with a strong discrete math component) in fact were accepted at a higher rate (34.5%) than the overal rate (27%). They also broke down into long and short submission rates the same way as non-DM papers.

2) Short papers provide an anchor for page lengths not at 12 (so that authors don't feel that their 6 page submission is viewed as inferior to a 12 page submission)

PZZT ! Wrong answer. Acceptance rates were not correlated with paper length. In fact many good 7-10 page papers were accepted. Compounding this was the fact that many short submissions had 7 pages of appendices (!).

3) Short papers allow for nascent and inter-disciplinary work.

This is a noble idea, but since we have reached the limit (135) of papers we can accept, any such short paper has to compete directly against a long paper, and invariably loses out. Basically, it is a zero-sum game at this point.

There was much wailing and gnashing of teeth at this point, but IMHO Adam's rather convincing presentation of the data quelled much discussion. After all, it's hard to have a strong opinion when there is clear data that contradicts it.

Will short papers die ? It's not clear. After one of the over 10 billion straw votes that we had, it was decided that the SODA 2006 PC would "take into consideration" the sense of the community, which was:

a) No extra tracks

b) Short papers MUST DIE (err... have problems).

### SODA wrap-up

still no paper reviews: wireless access at the conference was limited, and in a way this was a blessing. Instead of lugging my laptop around and fiddling with email in the middle of talks, I actually sat and listened (having to chair sessions helped as well). Not having the proceedings was a mixed blessing: most people felt that having access to the proceedings (or at least abstracts) would have made paper sampling a lot easier. On the other hand, I didn't have the urge to read the proceedings during talks.

Overall it was a nice conference, and Vancouver is a great town. For once, the hotel was quite pleasant, and the meetings rooms/lounging areas were just right.

over the next few days/weeks I will start posting some paper reviews, on whatever inspires me.

Overall it was a nice conference, and Vancouver is a great town. For once, the hotel was quite pleasant, and the meetings rooms/lounging areas were just right.

over the next few days/weeks I will start posting some paper reviews, on whatever inspires me.

## Tuesday, January 25, 2005

### John Baez

gave an entertaining talk on loop quantum gravity. He managed to hint at a surprising amount of math without losing the audience, and if the questions at the end were any indication, people enjoyed a rather different talk to the normal SODA fare.

p.s SODA proceedings update: in Montana and moving steadily forward.

p.s SODA proceedings update: in Montana and moving steadily forward.

### SODA business meeting

If I had drunk as much as prescribed, I'd be weaving right now. It almost seemed like people were finally getting tired of the endless discussions. Adam Buchsbaum did a deadly job of killing all feeble attempts to keep short papers alive (death by statistics was the coroner's report), and we shall see what the outcome is.

SODA 2006 will be in Miami (but not in Miami Beach alas). Cliff Stein will be the chair. It appears that SODA 2007 will either be in Monterrey, Mexico or New Orleans. Either way is fine with me :).

SODA 2006 will be in Miami (but not in Miami Beach alas). Cliff Stein will be the chair. It appears that SODA 2007 will either be in Monterrey, Mexico or New Orleans. Either way is fine with me :).

## Monday, January 24, 2005

### Pseudo-triangulations

A pseudo-triangulation is a polygon in the plane with only three convex vertices.

An interesting question about pseudo-triangulations is the following:

Is the number of triangulations of a planar point set at most the number of minimal pseudo-triangulations ?

From what I understand, this is true with equality if the points are in convex position. Herve Bronnimann talked about an experimental approach to validating this conjecture for small values of n.

p.s no wireless connection at the conference alas, so posting will be occasional.

p.s no wireless connection at the conference alas, so posting will be occasional.

## Sunday, January 23, 2005

### asides...

1. The SODA (and ALENEX) name badge has on its flip side a form that reads:

I didn't realize SODA had become such a heart-stopping adventure. Next thing you know we'll have FBI agents roaming the corridors.

2. The SODA proceedings will not be available at the conference because the train carrying them was derailed in Minnesota.

I kid you not.

p.s If ever we had an argument to reduce the number of papers accepted to SODA...

p.p.s On the bright side, I don't have to throw my back out lugging copies of the proceedings around with me.

IN CASE OF EMERGENCY

Name of person to contact

Phone # to reach this person

2. The SODA proceedings will not be available at the conference because the train carrying them was derailed in Minnesota.

I kid you not.

p.s If ever we had an argument to reduce the number of papers accepted to SODA...

p.p.s On the bright side, I don't have to throw my back out lugging copies of the proceedings around with me.

### ALENEX

So ALENEX started and ended today. The workshop started off with a keynote address by Bernard Moret on the Tree of Life and algorithmic issues in phylogeny. He set out an impressively complex landscape of problems, most of which required some serious algorithm engineering (fitting for ALENEX). One quote that I found rather amusing:

Later on, at the business meeting, we had the customary discussion of mindless statistics (how many papers were written by left-handed dwarfs from the eastern provinces of Transylvania ?). 15/60 papers were accepted, which is an impressive acceptance ratio. The submission rate appears to be relatively stable, and 15 is the maximum number of papers that can fit in a one-day workshop. Another mildly interesting stat was the fraction of papers submitted from Europe - 44.6%. This (to me) appears to be quite high, especially given that the workshop is in the West Coast.

Cathy McGeoch brought out a beautiful poster representing the history of NP-Completeness. It has a top section describing NP-hardness and complexity, and the main area of the poster is taken up by a graph in which vertices are NP-hard problems and edges are reductions. The nodes are colored by their Garey+Johnson classification, and immediately you see how SAT pops out as the source problem of choice for so many reductions.

The poster is being sold for $120 + $15 shipping (it's at least 36'' X 48''), and was designed by an ex-Amherst faculty member who now runs a graphic design company. No web pictures or thumbnails as of yet: I'll update this post when they appear. If you want to order a poster, send mail to Cathy [ ccm at cs dot REMOVEamherstTHIS dot edu ]. [Update: Click here for the poster website and a nifty Flash tool to navigate the poster.]

One of the motivations that Cathy mentioned was the lack of computer science art. It would be cool if we could create a poster for Chad Brewbaker's Complexity Zoo map.

In later postings I will mention some of the talks that I found interesting. I've been blogging from conferences for a while now, and I notice that I often feel the pressure to say something about every paper, for fear that by exclusion, I am making a statement about a talk/paper. Rest assured that this is not the case.

In related news, Lance inspires yet another theorist to start a blog. He is indeed the Blogfather of theory :).

Truth is not part of the vocabulary of algorithm designThis was when discussing how the goal of algorithms (optimization) differs from the goal of biology (scientific truth).

Later on, at the business meeting, we had the customary discussion of mindless statistics (how many papers were written by left-handed dwarfs from the eastern provinces of Transylvania ?). 15/60 papers were accepted, which is an impressive acceptance ratio. The submission rate appears to be relatively stable, and 15 is the maximum number of papers that can fit in a one-day workshop. Another mildly interesting stat was the fraction of papers submitted from Europe - 44.6%. This (to me) appears to be quite high, especially given that the workshop is in the West Coast.

Cathy McGeoch brought out a beautiful poster representing the history of NP-Completeness. It has a top section describing NP-hardness and complexity, and the main area of the poster is taken up by a graph in which vertices are NP-hard problems and edges are reductions. The nodes are colored by their Garey+Johnson classification, and immediately you see how SAT pops out as the source problem of choice for so many reductions.

The poster is being sold for $120 + $15 shipping (it's at least 36'' X 48''), and was designed by an ex-Amherst faculty member who now runs a graphic design company. No web pictures or thumbnails as of yet: I'll update this post when they appear. If you want to order a poster, send mail to Cathy [ ccm at cs dot REMOVEamherstTHIS dot edu ]. [Update: Click here for the poster website and a nifty Flash tool to navigate the poster.]

One of the motivations that Cathy mentioned was the lack of computer science art. It would be cool if we could create a poster for Chad Brewbaker's Complexity Zoo map.

In later postings I will mention some of the talks that I found interesting. I've been blogging from conferences for a while now, and I notice that I often feel the pressure to say something about every paper, for fear that by exclusion, I am making a statement about a talk/paper. Rest assured that this is not the case.

In related news, Lance inspires yet another theorist to start a blog. He is indeed the Blogfather of theory :).

## Saturday, January 22, 2005

### For the 1000th time, Bell Labs != AT&T !!!

I can understand fellow researchers being confused (OK I can't, but I can at least try), but the New York Times ?

With four titles of his own, Mr. Eslambolchi, who also directs Bell Labs and AT&T's network operations, manages engineers, technicians and researchers in 11 divisions and speaks directly to dozens of customers a month to hear what they wantRepeat after me: Bell Labs is Lucent, Shannon Labs is AT&T.

### SODA/ALENEX

Am at SODA/ALENEX right now: posting will be slow, but I will attempt to have some kind of summary of the daily activities. If anyone is reading this AND is at SODA AND doesn't have a blog of their own, feel free to email me to post conference updates here.

## Thursday, January 20, 2005

### Betti Numbers

It's been many days now since Afra Zamorodian announced his new monograph 'Topology and Computing'. Now that I finally got a chance to read an excerpt, I am encouraged ! Finally, I am hoping that there is a way to understand Betti numbers without needing an entire year's worth of study :).

Great job, Afra ! Topology is an area that has many intriguing connections with geometry and algorithms in general (Kneser's conjecture, the Kahn-Saks-Sturtevant partial resolution of the evasiveness conjecture), and we need books that can bridge the gap. Another "geometric' text is the wonderful book by Matousek on the Borsuk-Ulam theorem, and a more 'combinatoric' text in this regard is the survey 'Topological Methods' by BjÃ¶rner in the Handbook of Combinatorics.

Great job, Afra ! Topology is an area that has many intriguing connections with geometry and algorithms in general (Kneser's conjecture, the Kahn-Saks-Sturtevant partial resolution of the evasiveness conjecture), and we need books that can bridge the gap. Another "geometric' text is the wonderful book by Matousek on the Borsuk-Ulam theorem, and a more 'combinatoric' text in this regard is the survey 'Topological Methods' by BjÃ¶rner in the Handbook of Combinatorics.

## Tuesday, January 18, 2005

### It's already in the text. It just needs a close reading.

Lett3rs. coming to a screen near you...

## Friday, January 14, 2005

### Those stinkin' security intellectuals...

This is a cool quote:

Via BB.

p.s Matt Blaze used to work at AT&T Labs.

Tags: locks, cryptography

We have to nip it in the bud or soon there will be no security left after these intellectuals get through with us.This is the source: alt.locksmithing

Via BB.

p.s Matt Blaze used to work at AT&T Labs.

Tags: locks, cryptography

### Teaching...

I'm teaching a class, something that I don't often do, and have been discovering interesting differences (duh!!) between a one-hour talk and a 1.5hr lecture. A recent article on Slate excerpts a new book by Eric Liu called 'Guiding Lights', about teachers in different walks of life, and how they hone their craft. One quote from the article was interesting:

Like any good teacher, Bryan is a master of misdirection: working on a fastball to improve a change-up, using dry work without a ball to sharpen performance with a ball, and talking about how to keep a quiet head when, in fact, we were talking about how to keep a quiet mind.It's an interesting way of describing the work a teacher does. A review from Publisher's Weekly at the Amazon.com page talks of other techniques, like

receiving before transmitting—that is, tuning in to the student's unique qualities and motivations; unblocking and unlocking—helping students overcome their inner obstacles; and zooming in and out—breaking the subject down and then connecting it other matters.I'm curious to know what the full-time teachers think of this...

## Wednesday, January 12, 2005

### if I were an idle grad student...

Here would be a cool thing to hack:

HubMed is an RSS interface to PubMed (the equivalent of arxiv, but much better, for the bio/medical community). Plug your PubMed search into HubMed, and lo and behold, out pops a search with an RSS feed you can subscribe to. Think of it as a specialized Feedster for PubMed.

The CoRR now has an experimental full text search to go with their category searches. You could always subscribe to RSS feeds for new papers in specific categories. Wouldn't it be neat to have a Feedster-like interface for general text searches, so I could get all new papers that mention "art gallery" for example ?

It seems like it is not hard conceptually: a web form to process requests for searches, and a crawler that queries CoRR (along with some parsing goo to make XML).

HubMed is an RSS interface to PubMed (the equivalent of arxiv, but much better, for the bio/medical community). Plug your PubMed search into HubMed, and lo and behold, out pops a search with an RSS feed you can subscribe to. Think of it as a specialized Feedster for PubMed.

The CoRR now has an experimental full text search to go with their category searches. You could always subscribe to RSS feeds for new papers in specific categories. Wouldn't it be neat to have a Feedster-like interface for general text searches, so I could get all new papers that mention "art gallery" for example ?

It seems like it is not hard conceptually: a web form to process requests for searches, and a crawler that queries CoRR (along with some parsing goo to make XML).

## Tuesday, January 11, 2005

### What is the Fold ?

"This is your last chance. After this, there is no turning back. You take the blue pill, the story ends, you awake in your bed and cut whatever you want to cut. You take the red pill, you stay in OrigamiLand, and I show you how deep the creases go.

Remember: all I’m offering is the Fold, nothing more."

Via emmous

Remember: all I’m offering is the Fold, nothing more."

Via emmous

## Monday, January 10, 2005

### Scian Melt #6

Welcome, one and all, to the Scian Melt #6. The Scian Melt is a carnival of science, with a heavy dose of Indian spices. For a second helping, visit the Scian Melt homepage.

The terrible tsunami is constantly on our minds: Wikipedia has much more information about how a tsunami is formed, as well as links to the latest news on the disaster itself. If you are one of the ten remaining people on the planet who hasn't visited SEA-EAT, please do so, and contribute in whatever way you can.

Tony Denmark has a page of before-and-after scenes of devastation in Sri Lanka and Indonesia. The devastation in Banda Aceh is truly horrifying.

It is a cliche (but still true) that tragedies bring out the best in people, and remind us of the worth of those that we so easily dismiss in calmer times. Anna from sepiamutiny points out that the vast majority of men working to remove bodies in the most affected areas of Tamil Nadu are Dalits, or "untouchables" as they used to be called. Considering how so many others are shying away from dealing with the vast numbers of corpses and the imminent health catastrophe, they deserve our recognition.

In the wake of the disaster, controversy raged over whether the tsunamis could have been predicted, or if anything could have been done to lessen its impact. Janaki Kremmer at the Christian Science Monitor pens an article about how mangrove forests saved hundreds of villagers by forming a natural barrier between villages and the sea.

But along with true science comes the wackos. There are numerous conspiracy theories about the cause of the tsunami, with one of the more popular ones being an Israeli-Indian joint nuclear test. Arm your falsifier guns, folks !

In other news, Atanu Dey laments as to why Indians are prone to both reflexive self-bashing and a blind pride that obscures our true failings. He asks

To end this melt here's a nice page summarizing the history of Indian Mathematics (I am after all a computer scientist).

The next Melt will be hosted by MadMan: please send your nominations to melt [at] thescian [dot] com or madman [at] madmanweb [dot] com

The terrible tsunami is constantly on our minds: Wikipedia has much more information about how a tsunami is formed, as well as links to the latest news on the disaster itself. If you are one of the ten remaining people on the planet who hasn't visited SEA-EAT, please do so, and contribute in whatever way you can.

Tony Denmark has a page of before-and-after scenes of devastation in Sri Lanka and Indonesia. The devastation in Banda Aceh is truly horrifying.

It is a cliche (but still true) that tragedies bring out the best in people, and remind us of the worth of those that we so easily dismiss in calmer times. Anna from sepiamutiny points out that the vast majority of men working to remove bodies in the most affected areas of Tamil Nadu are Dalits, or "untouchables" as they used to be called. Considering how so many others are shying away from dealing with the vast numbers of corpses and the imminent health catastrophe, they deserve our recognition.

In the wake of the disaster, controversy raged over whether the tsunamis could have been predicted, or if anything could have been done to lessen its impact. Janaki Kremmer at the Christian Science Monitor pens an article about how mangrove forests saved hundreds of villagers by forming a natural barrier between villages and the sea.

But along with true science comes the wackos. There are numerous conspiracy theories about the cause of the tsunami, with one of the more popular ones being an Israeli-Indian joint nuclear test. Arm your falsifier guns, folks !

In other news, Atanu Dey laments as to why Indians are prone to both reflexive self-bashing and a blind pride that obscures our true failings. He asks

Does anyone ever ask the question:Well, as it turns out, the 92nd Indian Science Congress was held last week in Ahmedabad, with discussions on Indian pharmaceuticals, stem cell research, and disease prevention. It turns out that haldi (turmeric) is really really good for you. Research now shows that curcumin (an active ingredient of haldi) can be used to design effective anti-malarial drugs. What's more, curcumin has been shown to help stave off Alzheimer's, as well reduce plaque that may have already built up in the brain. Eat Indian food often, people !Why is India the way it is?... When was the last time you ever heard of a conference where serious people with lots of knowledge and understanding got together to examine that question?

To end this melt here's a nice page summarizing the history of Indian Mathematics (I am after all a computer scientist).

The next Melt will be hosted by MadMan: please send your nominations to melt [at] thescian [dot] com or madman [at] madmanweb [dot] com

## Sunday, January 09, 2005

### Hmmm...

Interesting:

These are organizations that have fired, threatened, disciplined, fined or not hired people because of their blogs:

1.) Delta Air Lines

2.) Wells Fargo

3.) Ragen MacKenzie

4.) Starbucks

5.) Microsoft (some say yay, some say nay)

6.) Friendster

7.) the Houston Chronicle

8.) the St. Louis Post-Dispatch

9.) Nunavut Tourism (Canada)

10.) the Committee on Degrees in Social Studies, Harvard University

11.) Maricopa County Superior Court of Arizona Self Help Center and Library

12.) Mike DeWine, US Senator (R-Ohio)

13.) the Durham Herald-Sun

14.) Kerr-McGee

15.) ESPN

16.) Apple (according to this blog entry AND this article)

17.) Statistical Assessment Service (DC nonprofit)

18.) Minnesota Public Radio

19.) The Hartford Courant

20.) the International Olympic Committee (barred athletes from blogging during the Olympics last summer)

21.) Health Sciences Centre, Winnipeg, Manitoba, Canada (?)

22.) the National Basketball Association (NBA)

## Thursday, January 06, 2005

### This could be a description of my day...

## Tuesday, January 04, 2005

### What do you believe is true...

...even if you cannot prove it ? This was the question posed by Edge.org to a number of scientists, intellectuals, and thinkers of various hues. There have been numerous comments on this article, and a spread in the NYT, but what I found interesting was the choice of people interviewed. There were extremely few computer scientists in the bunch, and not a theoretician among them ! John McCarthy thinks that the continuum hypothesis is false...

Any thoughts on what statements we believe to be true, even if we can't prove them ? P ? NP is not included :)

Any thoughts on what statements we believe to be true, even if we can't prove them ? P ? NP is not included :)

### How did I miss this ?

A number of us were fretting about how Numb3rs would caricature mathematicians, while NBC slipped this right under our noses:

NBC's new sitcom, "Committed," a series centered on the romance between Nate (Josh Cooke), an obsessive-compulsive math genius and his nutty girlfriend, Marni (Jennifer Finnigan), makes it clear: psychological disorders are the next big thing.As for the character 'Nate':

Nate, a math genius whose family makes the Tennenbaums seem like the Partridge family, works in a used-record store and nurses his fixations: he has an obsessive fear of elevators, blocked emergency exits and throwing things out. One episode revolves around Nate's attempts to keep Marni from seeing his apartment, which looks like a cross between the CollyerBrothers' brownstone and the schizophrenic mathematician's garage in "A Beautiful Mind"The review ends with this rather cruel jab:

Mr. Cooke is appealing in the role of Nate, but he seems a little wholesome for someone who makes Venn diagrams to map out a conversational point.Hey ! Watch it there ! Us borderline-psychotic obsessive-compulsive math geeks have feelings too.

### Not that I am complaining...

But it seems a bit odd that the first link of the google search "soda 2005" is a page from the Geomblog, and even worse, the official SODA 2005 page doesn't appear anywhere in the top 50 links for this search.

### On conference loads

The topic of acceptance ratios and PC sizes has been discussed to death, and I will start by saying that I have nothing new to add to this debate :). However, on the issue of reviewer load, one new idea had popped up a while ago:

Another interesting chart in this letter was a plot of submissions and acceptance ratios for four major conferences (SIGMOD/STOC/ISCA/PODC) over the past 5 years.

What I find most striking about this graph is that on the one hand, SIGMOD submission counts have gone up (pretty much what one would expect), but the acceptance rate has held roughly steady, implying the conference has grown in size over the years. In STOC, on the other hand, submission counts rose, and then remained steady, but acceptance rates have dropped precipitously ! Seems strange that this would happen.

One of my pet peeves has been hearing a slew of theories trotted out to "explain" the increased submission rate in a variety of conferences (though not STOC); my gripe has been that none of this theories have anything more to back them up than plausible sounding words. Interestingly, Patterson's letter has something to say about this as well:

* To handle the case of recycled papers that go from conference to conference in the hope of finding reviewers that haven't seen them:I was reading the Dec issue of CACM (all right, I admit it: I do read the CACM, but ONLY because this issue was on the blogosphere!), and in David Patterson's letter was this nugget:

- Create a repository where all submitted papers are registered. When a paper is submitted to a conference, a link is set up, and then when reviews return, they are filed with the paper. If the paper is submitted again, the reviews are there to see.

Perhaps the most novel approach to the whole problem is being taken by the database community under the leadership of SIGMOD. The three large database conferences are going to coordinate their reviewing so that a paper rejected by one conference will be automatically passed along to the next one with the reviews. Should the author decide to revise and resubmit the paper, the original reviewers will read the revision in light of their suggestions. The next program committee would then decide whether or not to accept the revision. Hence, database conferences will take on many of the aspects of journals in their more efficient use of reviewers' efforts in evaluating revisions of a paper.I assume the three bigs are SIGMOD, PODS and VLDB ? It would be interesting to see how this works out. There are pros and cons in carrying prior reviews along with a paper, and a lab experiment such as this might reveal interesting side effects.

Another interesting chart in this letter was a plot of submissions and acceptance ratios for four major conferences (SIGMOD/STOC/ISCA/PODC) over the past 5 years.

What I find most striking about this graph is that on the one hand, SIGMOD submission counts have gone up (pretty much what one would expect), but the acceptance rate has held roughly steady, implying the conference has grown in size over the years. In STOC, on the other hand, submission counts rose, and then remained steady, but acceptance rates have dropped precipitously ! Seems strange that this would happen.

One of my pet peeves has been hearing a slew of theories trotted out to "explain" the increased submission rate in a variety of conferences (though not STOC); my gripe has been that none of this theories have anything more to back them up than plausible sounding words. Interestingly, Patterson's letter has something to say about this as well:

ACM's research conferences are run by its Special Interest Group (SIGs). I've been working with the SIG Governing Board to help form a task force to study this issue, looking at why submissions are increasing and documenting approaches like those discussed here, and to evaluate their effectiveness. They plan to report back in early 2005. If you have any comments or suggestions, please contact task force chair Alexander L. Wolf (alw@cs.colorado.edu).

## Sunday, January 02, 2005

### A Gallery of Visualization

It appears that art and geometry go well together. Take George Hart's geometric sculptures, or the Voronoi building. I found this intriguing gallery of visualization via del.icio.us/math:

The above picture is a visualization of nodes in a graph evolving by the rule:

A.Move close to friends but not closer than some minimum distance.

B.Distance self from non-friends as much as possible.

Subscribe to:
Posts (Atom)