USTCON is in L

Read all about it !! Lance has the annoncement, and David Molnar has additional reading.

Note that this paper could also have been titled in 4 letters:

SL = L

The fever catches on...

I promise (or at least try to promise) that this will be my last cartogram post. Looks like map fever has caught on a big way since my first cartogram. If you are not already sated by maps, maps and more maps, check out the extensive resources on election cartograms at UCSB provided by Sara Fabrikant.

Her maps have Alaska and Hawaii (which I and others shamelessly ignored). I must say that Alaska looks like an albatross in this map.

Making your own maps...

Since I first posted the cartograms, many people have emailed me asking if I could modify the cartograms to do various kinds of displays. Although changing color schemes is easy, changing the map itself is not (since I didn't generate the polygons for the map myself).

Anthony Robinson, a master's student at Penn State, works on various aspects of geographic visualization within the geoVISTA center, and has provided a toolkit developed by folks at Penn State that allows you to download Election 2004 results and play with them inside an exploratory analysis tool. He also provides the election data to work with !

Definitely check it out if you want to create your own maps; the folks at Penn State have been doing great work in scientific visualization for a while.

Color schemes

One of the side discussions around the purple map was: what is a proper color scheme to color such a map, beyond just a red-blue-purple mode. Many ideas were suggested, and some of them are reflected on the page, but till a commenter mentioned it, I didn't realize that cartographers have studied this problem in great depth.

Cindy Brewer, a cartographer at Penn State, has designed a beautiful web site that helps with coloring choropleths (the technical term for maps where each region is colored with a single color). You decide what kind of data you have and how many categories of colors you needs, and the flash applet generates a color scheme, as well as color values in a variety of color maps (RGB/CMYK/etc).

Using a bivariate 10-value divergent color scheme (color spreads out from the middle of the data range), here is the Election 2004 cartogram:

For more maps, visit my new cartogram page.

More cartograms and some histograms

Gartner, Shalizi and Newman have another cartogram, made using a different ("diffusion") approach.

They also had some histograms of vote totals on this page, which they took down because of some anomalous values. I got the idea to do something similar, and here is the result (click for the big pic).

The 'Purple Haze', revisited.

[Update: Nov 8]: More color schemes (one based on colorbrewer.org) and a toolkit to make your own maps !

By now, Robert Vanderbei's purple map of the voting counts in Election 2004 has crisscrossed the internet several times. On his web page, he answers some questions about these maps:

Can you warp the counties so that each county's area is proportional to its total vote count? Such warped maps are called cartograms. There are already several of these at the state-by-state level on the web. I haven't seen any at the county-by-county level. A few years ago I collaborated briefly with David Dobkin and Stephen North on algorithms for producing cartograms. I can say that making a cartogram with so many individual elements (counties) would be very difficult.

Cartograms are indeed hard to compute: this is an interesting geometric problem, as Jeff Erickson also points out.

As it turns out, the place I work at does cartograms, and quite well at that ! Stephen North (the one mentioned above) and colleagues have developed methods for computing cartograms and I used their approach to create a cartogram of the election results. I used the data from a paper by Daniel Keim, Stephen North, and Christian Panse that uses the medial axis to construct a cartogram.

[UPDATE: the original maps had a problem in labelling Nevada because of a mismatch between county names in the two data sets: the new maps shown here reflect the correction. Thanks to the commenter who pointed this out.]

I used a variety of color schemes: for more information, and larger pics, see my new cartograms page. (note: for formatting purposes I used HTML to scale the images; if you download the image, it will be bigger)

1. A Vanderbei-like color scheme, where the relative proportion of votes for Bush or Kerry turns the county red or blue respectively: purple regions are roughly even.






2. The winner-take-all color scheme: a county that Bush won is marked in red, and one that Kerry one is marked in blue.





3. Red-blue (suggested by a poster on the blog). Start with a baseline of white for equal vote-share. as the vote percentage for the winner increases, increase the strength of red or blue appropriately.






4. Grayscale (suggested by Kathryn Myronuk). Start with a baseline of white for equal vote-share. As the vote percentage for the winner increases, make the color grayer.





5. ROYGBIV (suggested by Kathryn Myronuk). Again, white is neutral, but go towards the R side or the V side of the color spectrum depending on who wins and how much (thresholds at .7, 0.6, .53)

It takes a while getting used to a cartogram, and having to ensure that counties still touch after being inflated can make the problem quite difficult to solve while still retaining an overall representative shape. However, it is interesting to see how large California and the North-east really are in context, and how the entire middle-west of the country shrinks.

As far as I know, the complexity of computing a cartogram (where the typical formulation would be to minimize some error metric on the discrepancy between the area of a region and weight associated with it) is unknown, and is probably NP-hard (I once thought I had a proof for NP-hardness for rectangular cartograms, but it foundered). However, much of the challenge in cartogram design comes from trying to balance accuracy and aesthetics; the map when distorted should still look like the original map !

For more on this, check out the AT&T Info Viz page on spatial data transformation.

Unicode is cool

This is my name, typed in Hindi using the INSCRIPT keyboard.

सुरेश वेंकटसुब्रमणियन

and in Tamil:

சுரேஷ் வெங்கடசுப்ரமணியன்

In order to do this earlier, I needed all kinds of LaTeX goo...

Incidentally, this site has all kinds of useful information on entering and reading characters from different languages.

Aside: I just realized that Safari mangles the fonts: Hindi slightly, but the Tamil is completely unrecognizable. I can understand that the mapping table for Tamil is not loaded, but the Hindi rendering has the right map, but is wrongly rendered. Interesting...

Another e-publishing model

Another example of how ease of publishing on the internet is making new models of academic discourse possible: Brad DeLong points to the Encyclopedia of Economic and Business History, a new article collection that

is designed to provide students and laymen with high quality reference articles in the field. Articles for the Online Encyclopedia are written by experts, screened by a group of authorities, and carefully edited. A distinguished Advisory Board recommends entry topics, assists in the selection of authors, and defines the project's scope.

This places it somewhat below a survey journal in terms of scholarly status, but above other web resources for laymen like Wikipedia or Mathworld or even ScienceWorld in terms of reliability and academic rigor.

It's a laudible endeavour. I suspect it works well in this area because economics have a tradition of public writings in addition to their academic work (as evidenced by the number of economics blogs). Given the levels of economic illiteracy among the public, and the importance of economic issues in making policy, such a resource can be of immense benefit for those of us trying to follow the often arcane and impenetrable discussions that swirl around issues like outsourcing, the economy, social security and tax cuts.

E-voting: The Blog

A new computer science blog, this one on e-voting. It has been started by a number of experts in e-voting, including AT&T Labs alumnus Avi Rubin. Here is the first message, posted by Ed Felten:

Welcome to evoting-experts.com.

Our panelists will be posting news and commentary on e-voting issues. We hope our site will serve as a central source of information and insight about e-voting, straight from some of the leading independent experts.

This is a non-partisan site. Our goal here is not to advance any political agenda, but to help ensure that all votes are counted fairly and accurately, and to provide honest expert commentary to the public and the press.

Given the amount of scrutiny that this election will face, and the amount of FUD that will be generated by the parties and the media over voting processes, this will hopefully be a good resource to understand the real issues behind e-voting and how it affects this year's prelude to a recount.

Mathematics vs Statistics

This amusing excerpt is from an interview of Bradley Efron, inventor of the bootstrap method in statistics:

I thought I was going to be a mathematician. I went to CalTech, and I think I would have stayed a mathematician if mathematics was like it was a hundred years ago where you computed things, but I have no talent at all for modern abstract mathematics. And so I wanted to go into something that was more computational. After CalTech I came to Stanford. And statistics was definitely better.

Incidentally, Efron's book is a very nice introduction to the bootstrap method, striking that delicate balance between 'So how do I use this stuff' and 'So why does this really work'

Some NSF info

I would have called this 'NSF news' except for the fact that it is over three months old. The CRA had a conference in Snowbird in July, and among the presentations there was one on trends in NSF funding, by Greg Andrews from CISE. The presentation itself is quite short: some interesting facts...

• Submissions to CISE have gone up 125% from 1997-2003, and are expected to grow even faster in 2004.
  
• The CCF (which includes most of theory, graphics and geometry, but not databases) had a 15% accept rate for CAREER awards, but only 5% for other proposals.
• It appears that there will be no non-CAREER competition for CCF grants in FY 2006. This is attributed to budget pressures, and it is indicated that things will be 'back to normal' in FY 2007.
  

As a comparison, acceptance across the board in CISE is roughly 16%. CNS (Computer and Network Systems) had much higher success rates (30% CAREER, 17% otherwise).

Not being at a university, I don't know how much of this is already old news. This post was prompted by a lunchtime discussion on pressures to publish, write grants etc. It also appears from anecdotal evidence that there are more people submitting more proposals than ever (akin to the situation with paper submission to conferences).

Dynamic Optimality - some progress....

A binary search tree is probably the most basic data structure in computer science, and is one of the first structures you come across when learning algorithms. Given a set of keys and an order defined on the keys, a binary search tree maintains the property that the key of a node is greater than all keys of left descendants and less than all keys of right descendants.

One of the most important outstanding problems in data structures is designing an optimal BST. Structures like red-black trees and splay trees can be shown to take O(log n) time (amortized) per insert/delete/find operation, and this is tight, in the sense that there exist sequences of updates of length m for which Omega(mlog n) tree operations are required. For charging purposes, a single 'splay' or 'rotation' takes one unit of time.

However, if we restrict ourselves to a static universe, with only searches, can we do better with respect to the optimal offline solution ? The Dynamic Optimality conjecture, first stated by Sleator and Tarjan, conjectures that splay trees cost only a constant factor more than an optimal offline algorithm. Note that this optimal algorithm must change the tree (hence the term 'Dynamic'); if the optimal offline algorithm is forced to choose a fixed tree, then splay trees are asymptotically optimal.

A new FOCS 2004 paper by Demaine, Harmon, Iacono and Patrascu takes a crack at the Dynamic Optimality conjecture, presenting an algorithm that comes with O(log log n) of the optimal offline solution.

Elections can be educational !

Jordan Ellenberg, novelist and math prof at Princeton, does the impossible: he provides a lucid explanation of both Bayesian analysis and Nash equilibria in the context of electoral strategy.

He also reads an awful lot...

Update: We could have a course on electoral math: Tall, Dark and Mysterious points out yet another set of articles on election math, this time focussing on the Banzhaf power index (a method for determining the relative power of blocs in a block voting system). For extra credit, consider the following:

The runtime of the programs doing these computations is already pretty high (O(2ⁿ)), but I wonder if there are any probabilistic variations on this index as applied to the electoral college.

Is there a more efficient approach ?

INDUCE is dead ?

A few months back, I had mentioned an abomination known as the INDUCE Act, that would generalize wildly the class of actions that could be construed as copyright infringement (e.g. making a device that could be used for copyright infringement). It is worth pointing out here that the software industry (one of the largest holder of copyrights) was against this bill.

Congress (or more specifically Orrin Hatch) was trying to get this bill passed, and apparently it appears to be DOA at least for this term. Read more about it in this engadget interview with Wendy Seltzer, an attorney with the EFF.

Back to my roots :)

The first computer I ever programmed on was the ZX Spectrum 48k (yep, 48K memory)

External storage was a tape recorder (and watch that volume control otherwise the data transfer gets hosed !). I wrote BASIC programs, and a lot of assembly code video games. Come to think of it, I learnt some of my first AI techniques on this machine.

I also got an early lesson in technology envy; a friend of mine then acquired the 128k Spectrum, and thus I went very quickly from king of the hill to insanely jealous second-best :)

This nostalgic rant was brought upon by this site, allegedly one of the oldest continually running websites on the web.

Didactic Writing/Research

William Gibson talks about writing, and didactic novels, arguing that a novel loses aesthetic quality if it seeks to further a point of view. In another way of saying it,

...no genuinely valuable interrogation of reality can take place, and the result will be a literary virtuality built as exclusively from the author's expressed political philosophy as that author can manage. This is best understood, an excellent teacher of mine said, by asking ourselves whether or not a fascist can write a good novel.

...A fascist can't write a good novel because writing a good novel, in the end, is about relinquishing control of the text.

In a way, this could be true for research as well. In theoretical work we often possess a hammer, and go hunting nails to pound, but some of the best kind of research is the kind that beautifully slots into the problem being addressed, to the extent that one can only say 'How else could this problem have been tackled ?', and yet, possesses a generality (akin to universal truths in good literature) that appeals to our shared aesthetic of beauty and enriches the field as a whole.

Proof parodies...

More proof parodies, this set more in the line of philosophical proofs rather than mathematical proofs (via Oxblog).

All the 'proofs' deal with proving the claim 'p', and here is one of the best;

Most people find the claim that not-p completely obvious and when I assert p they give me an incredulous stare. But the fact that they find not- p obvious is no argument that it is true; and I do not know how to refute an incredulous stare. Therefore, p.

Counter-examples

Mathematics has a long tradition of using counter-examples as a way of illuminating structure in theory. Especially in more abstract areas like topology, canonical counterexamples provide a quick way of teasing out fine structure in sets of axioms and assumptions.

A brief foray through Amazon.com revealed catalogues of well known counter examples in topology, analysis, and graph theory. On the web, there are pages on counterexamples in functional analysis, Clifford algebras, and mathematical programming.

What would be good candidate areas for a list of counter-examples in theory ? Complexity theory springs to mind: simple constructions (diagonalization, what have you) that break certain claims.

In combinatorial geometry, one might be able to come up with a list of useful structures. Personally, I find the projective plane to be a useful example to demonstrate the limits of combinatorial arguments when reasoning about geometric objects.

FOCS attendance.

Adam Klivans notes that FOCS attendance is down, to about 172 registered attendees (which is like the reverse of announced attendance at sports events; more people show up than the official registered list), in comparison to STOC 2004, which had 100 more people.

The number of papers accepted at STOC this year was 72, in comparison to 62 at FOCS. In general though, (and I only went back a few years because I got tired of opening proceedings), STOC appears to accept 15-20 papers more than FOCS on average (75-80 vs 60-65). There was no significant submission increase (surprising given the trend lines for other conferences), and so one can only surmise that location had at least something to do with the low attendance. After all, if you are submitting (and getting accepted) more papers than before, and if funding is down, you'd have to be pretty careful about choosing meetings to go to, especially if you are not presenting, and are thus not constrained to attend.

Although the number of accepted papers is not out of the norm for FOCS, one does have to wonder whether there are really only that few papers worth accepting ? I suspect this is constrained by the whole multi-track vs single-track, conference-as-prestige-stamp vs conference-as-meeting-place issue, and FOCS represents one extreme point.

Making scientific promises

Today, Arnold Schwarzenegger endorsed a proposition supporting funding for embryonic stem cell research. One of the many claims made by supporters of stem cell research is that it can help find a cure for Alzheimer's Disease, which afflicts nearly 3% of Americans between the ages of 65 and 74.

The concept of using embryonic stem cells to cure such diseases is tantalizing: in principle, the idea that such cells can be "nudged" into forming different kinds of adult cells indicates that cells (like brains cells) that do not regenerate can be replaced/replenished using stem cells.

What worries me though are the kinds of claims that are being made on behalf of stem cell research. Strategically, one can understand the desire to relate this to actual disease prevention (almost all NIH grant proposals mention a connection cancer in the first few paragraphs !), but it also appears at least plausible that there is a long way to go from the basic science of stem cell development to an actual disease treatment. Suppose a cure for Alzheimer's is really fifty years away, or longer. Is there a risk of a 'crying wolf' effect, where the promises of the research are so far that policy makers start becoming more skeptical ?

The reason I even bring this up is because I am reminded of a similar plight that overtook AI after its heyday in the 60s. Extreme amounts of hype, and the claim that soon computers could mimic humans, gave way to a serious backlash, and then finally a more nuanced understanding of the potential and limits of AI-related disciplines (fields like robotics/vision/learning appeared to flourish once they were not bound to the chains of "intelligence" and had more specific, local goals).

This may sound heretical, but sometimes working away from the limelight can be a lot better for a field; the real questions can be answered without having to worry about politics and controversy entering the picture (as in warming, global).

There is an element of blaming the victim here, I admit. After all, stem cell researchers would probably have been content to labor in obscurity if the issue hadn't been brought front and center by administration policy way back in 2001. Critics may complain that there is a serious ethical issue at stake here; I actually feel the ethical dilemma is more manufactured than real, hinging as it does on 'angels on the point of a pin'-like discussions about exactly when life starts.