"Geometry is not patented"

From Game 4 of the first-round playoff series between Miami and Chicago, Bill Walton and Steve Jones are arguing about whether a particular Heat offensive set was a triangle or not, and Walton says:

Geometry is not patented, Steve.

Indeed.

Categories

• miscellaneous

Inadvertent Hashing and CDDB

Most people use the CDDB either knowingly or unknowingly. It's the backend to most computer CD players that downloads track/title information from a central site when you're playing a CD. Most player software allows you to add in information if CDDB doesn't return a hit, and I've done this every now and then. But overall I have been amazed by the hit rate of CDDB.

I assumed that CDs contained all the track information, and many do. But apparently, CDDB exploits an inadvertent hashing mechanism: the sequence of track times.

The CDDB database has information that allows your computer to identify a particular music CD in the CD drive and list its album title and track titles. Their service is used by RealJukebox, MusicMatch, WinAmp, and others. The title information is not stored on most CDs. The only information in the CD data is the number of tracks (songs) and the length of each. This is the information your CD player displays. What CDDB does is let the software on your PC take that track information, send a CD signature to CDDB through Internet protocols (if you're connected) and get back the titles. It works because songs are of relatively random length. The chances are good almost all albums are unique. (Figure there are about 10 songs on an album, and they each run from a minute and a half or so to three and a half minutes long, so the times vary by 100 seconds. There are 100x100x...x100 = 100**10 = 10**11 = 1 hundred billion = an awful lot of possible combinations.) An album is identified by a signature that is a special arithmetic combination of the times of all the tracks.

You'd figure that CDDB just bought a standard database with all the times and titles. Well, there wasn't one. What they did was accept Internet-relayed postings with the track timing information and the titles typed in by a volunteer.

Categories

• algorithms

computers on stamps

Ultra neat (via BB). The irony of computers on stamps, considering what computers, (and email) have done to the postage business...

Categories

• miscellaneous

on vision...

if you haven't already, do read Luca Trevisan's essay on perspective and taste in theoryCS.

Categories

• community

Bias in paper reviewing

Nowadays, I spend my time looking the most emailed articles on the NYT (or more uncharitably, "rating the competition"). An interesting Op-Ed from Sunday talks about bias in decision-making, and some of what the author says provides an interesting perspective on how we review papers.

Unlike in many other areas of computer science, theory papers are not reviewed double-blind; reviewers in general know the identity of the authors of a paper. I will say upfront that I don't think there is a real problem with this approach. It's not that I think that we are saintlier than reviewers in other disciplines; it's just that a combination of the nature of the subject and the value system of the area makes objective evaluations a little easier. However,

A Princeton University research team asked people to estimate how susceptible they and "the average person" were to a long list of judgmental biases; the majority of people claimed to be less biased than the majority of people. A 2001 study of medical residents found that 84 percent thought that their colleagues were influenced by gifts from pharmaceutical companies, but only 16 percent thought that they were similarly influenced.

We'd like to think that we can "factor out" the influence of author names when reviewing, but

Dozens of studies have shown that when people try to overcome their judgmental biases — for example, when they are given information and told not to let it influence their judgment — they simply can't comply, even when money is at stake.

What's also interesting is how we make decisions with limited information,

...researchers asked subjects to evaluate a student's intelligence by examining information about him one piece at a time. The information was quite damning, and subjects were told they could stop examining it as soon as they'd reached a firm conclusion. Results showed that when subjects liked the student they were evaluating, they turned over one card after another, searching for the one piece of information that might allow them to say something nice about him. But when they disliked the student, they turned over a few cards, shrugged and called it a day.

Or if you dislike a paper, you look for evidence to reject it, and if you like it, you look for evidence to champion it (rather than looking for evidence first, and making a judgement later).

And yet, all the people who scream 'Bias' when papers submitted to single-blind reviewing are rejected don't necessarily have a point:

And yet, if decision-makers are more biased than they realize, they are less biased than the rest of us suspect. Research shows that while people underestimate the influence of self-interest on their own judgments and decisions, they overestimate its influence on others.

What does all of this mean ? I am more biased than I think, but less biased than you think. It's good to keep that in mind (at least the first part), when reviewing papers. It's basic psychology after all.

Categories

• community

Author Ordering, II

In the comments to my previous post, Janos Simon points out a pair of hilarious articles by Martin Tompa that were published in SIGACT News in 1990. The title of the first one is 'Figures of Merit', and in it, Tompa proceeds to define measures like the spotlight factor (basically the likelihood that you'd be first author if your co-authors were chosen randomly), and the coefficient of obliviousness (roughly speaking, how indifferent to fame you are by choosing co-authors prior in the order to you).

In his second article, Tompa updates the calculations after a year. As he puts it:

The purpose of this survey is to bring the community up to date on the most recent bounds, so that we may collaborate to improve them

I don't do the original articles justice with my dry rendition of their contents. You have to read them to encounter gems like:

There is one known instance in which a resourceful Ph .D . student named Yehuda
outspotlighted his advisor Shimon Even . When it came time to publish the results of
their collaboration, Even announced his inevitable intention of being first author. Yehuda responded by legally changing his name to Bar-Yehuda.

and, in his acknowledgements:

I thank the numerous contributors who inundated me with suggested additions after the Follies presentation, I can only wish that my serious research would stimulate half as much enthusiasm in the community.

The best line was a 'disacknowledgement' in part II (you'll have to read the articles for it to make complete sense):

Avi Wigderson refused to collaborate with anyone later in the alphabet, even in the interest of scientific advancement.

Update (4/16): Avi Wigderson reconsiders after 15three years of (unknowing) resistance !!

Categories

• community

Author ordering on papers.

We order authors alphabetically in theory papers. The reasons for this are numerous, and not relevant; what's relevant is that this is often different from other CS communities, where the first-author, , last-author norm is usually followed (first-author being the person who did all the work, and last-author being the PI on the project).

I'm all for alphabetical ordering: it's easy and avoids annoying and often impossible-to-resolve discussions about who did "more" work on a paper. Note that it's easy to identify who did what; what's harder is comparing the relative merit of contributions, especially in the multi-authored extravaganzas that are common in theory.

It turns out though that alphabetical ordering may have one pitfall, at least in economics:

...a new paper (free, working version, Winter 06, JEP) demonstrates that these effects have important consequences for careers in economics. Faculty members in top departments with surnames beginning with letters earlier in the alphabet are substantially more likely to be tenured, be fellows of the Econometrics Society, and even win Nobel prizes (let's see, Arrow, Buchanan Coase...hmmm). No such effects are found in psychology where the alphabetical norm is not followed.

Well, I don't know about tenure, but I do know about ACM Fellows and Turing Award winners. I'm too lazy to do the linear regression that the authors do for their plots, but I will throw out these two tidbits: 60% of Turing award winners (30/50) have their last names in the first half of the alphabet [A-M], compared to 40% (20/50) in the latter half [N-Z]. With Fellows, the split is 63% (347/554) to 37% (207/554).

I don't know how the authors of this paper normalized against any skew in the base population of economists, and the numbers I quote are subject to the same objection. But just in case, call me Suresh Enkatasubramanian from now on.


Update (4/14): An anonymous poster and D. Sivakumar have been working hard to debunk my claim, successfully so far ! Anonymous points out that the percentage of names in [A-M] in their phone book is around 63%, and Siva reports that going by the DBLP database, around 62% of all authors are in the [A-M] range as well (the 50% cutoff is at K apparently). Now, although this "explains" my quick back of the hand statistics, it leaves two possibilities:

• If one did the linear regression that the authors of the original paper used, one would get the same results
• Even the authors of the original paper didn't correct for the baseline (and frankly, after reading their paper twice, I don't see where they did, but I can't imagine that they didn't).
  

A third point worth making is that CS has mixed policies on author ordering. Only theory consistenly uses alphabetical ordering, so it can be argued that the data cannot be used to infer anything at all.

Categories

• community

It's Vortex time...

Get your auras here ! And don't say you weren't warned. From the NYT:

A few years ago, USA Today called Sedona the most beautiful place in America. At sundown, that doesn't begin to cover it. And it's not just the views. There's a vibe in the air, something not quite audible, a kind of metaphysical dog whistle that calls people out to have a look around and to try to feel something that, if you're not a committed New-Age pilgrim, is hard to put into words. Nowhere else in this country does a natural setting feel so much like the inside of a soaring pantheistic cathedral.

The Fib

Gregory K proposes a new form of mathematics-based poetry: the "Fib". The idea is simple: each line of the poem must have a number of syllables that equals the number at this position of the Fibonacci sequence. Example:

One
Small,
Precise,
Poetic,
Spiraling mixture:
Math plus poetry yields the Fib.

As Clive Thompson points out,

Even more lovely is the fact that the Fibonacci sequence officially begins with a zero. That means that the true first line of every Fib is always the same: Silence.

Start with a moment of rest. How beautiful.

Here's my 'umble contribution:

I
like
to blog.
Frequently.
Theory matters.
Computer science (theory)
is my home and geometric algorithms are
sublime. Let P be a set of points in general position in the plane. Amen.

Update (4/14): I was mentioned in the New York Times Book Section !

Categories

• miscellaneous

CS blogs

Actually, there are far more CS blogs than the list David points to: here's an OPML file that you can import into a blog reader. It has 40+ blogs that are in some way connected to computer science.

Categories:

• blogs

SODA 2007

The CFP for SODA 2007 is out (thanks, Jeff). The humungous size of the geometry contingent is balanced by the humungous size of the commitee. This commitee has 27 folks, an increase of 4 over SODA 2006 and 2005. Submission counts have been going up by a little under 10% each year, and I guess Hal Gabow is also trying to reduce the load on each committee member: 500 * 3/27 = 55.56. Good luck, folks !!

In other news, short papers are still dead. May they rest in peace

Categories

• soda
• cfp

Mathematical Poetry

David Corfield writes a wonderful blog called "Philosophy of Real Mathematics", where he addresses

"what leading mathematicians of their day have achieved, how their styles of reasoning evolve, how they justify the course along which they steer their programmes, what constitute obstacles to these programmes, how they come to view a domain as worthy of study and how their ideas shape and are shaped by the concerns of physicists and other scientists".

His latest entry points us to another beautiful piece of mathematical poetry, this one written by no less than James Clerk Maxwell. The background for this poem is described in Corfield's post: I merely reproduce here the first stanza of the poem:

My soul's an amphicheiral knot
Upon a liquid vortex wrought
By Intellect in the Unseen residing,
While thou dost like a convict sit
With marlinspike untwisting it
Only to find my knottiness abiding,
Since all the tools for my untying
In four-dimensioned space are lying,
Where playful fancy intersperses
Whole avenues of universes,
Where Klein and Clifford fill the void
With one unbounded, finite homoloid,
Whereby the infinite is hopelessly destroyed.

Categories:

• miscellaneous

60th birthdays

[Lowerbounds,Upperbounds] advertises MillerFest, a celebration of Gary Miller's 60th birthday. On April 24-25, Rutgers and DIMACS are hosting a workshop in honor of Joel Spencer's 60th birthday. Frieze Fest, last October, commemorated Alan Frieze's 60th birthday. I also hear that Peter Winkler's 60th will be commemorated next year, again at DIMACS.

What started the tradition of 60th birthday celebrations for researchers ? If you google '60th birthday mathematician', you get a very large number of links, as you do if you replace mathematician by physicist or economist. I looked all over attempting to find a source for this tradition, but it appears to go quite far back. I was wondering if any of my readers had any ideas about this...

Categories

• miscellaneous