Making People Fly

The advertising tagline for the 1978 movie Superman

You'll believe a man can fly!

I grew up at a magical time for movies when special effects started to look almost realistic. The 15-year me was truly amazed that Superman actually did look like he flew, special effects done by careful camera work and very thin wires. Today actors where larger cables and harnesses digitally removed in post-production, unless the entire flying sequence is entirely computer generated.

Back then we still had limits to special effects which made movies like Star Wars all the more impressive. Back then hidden supports were needed to make the hovercraft float. George Lucas has since gone back and added digital creatures to the original films, blasphemous to us fans who grew up with the movie.

We have reached the point where special effect can achieve pretty much anything the director can imagine. This gives some advantages, forcing movies like Dark Knight, Iron Man and Spiderman to rely on strong stories, characters and actors since special effects alone no longer sells movies (see Speed Racer). But no longer can we amaze teen-age kids with new technologies that make the seemingly impossible that come to life. Kids who, amazed by some of this work, done by computers, made them a hobby and then a career.

Biomedical engineering seems to be the new expanding major, at least at Northwestern. Computer Science needs to regain that coolness factor to attract the CS majors we and society continue to need.

comp Geom/MD Theory day/New Blog/Bond, James Bond

1. The call for papers for the 25th Annual Symposium on Computational Geometry is here. submissions are due December 1.
2. 20th Maryland Theoretical Computer Science Day! Tuesday, Oct 14, 2008! 9:30am -- 4pm (see online schedule for details)! AVW 2460 A.V.Williams Building! schedule
3. A new Theory Blog! It will emphasize applications to Global Health Metrics! Author is Abraham Flaxman! The website is linked to by our site.
4. A new James Bond Movie will be out soon Quantum of Solace. The Plot: Bad guys build a quantum computer and begin factoring numbers and breaking codes, but then Lance Fortnow and Scott Aaronson write a paper that shows their approach is flawed!

An Accidental Theorem

First a reminder that the FOCS early registration/hotel registration deadline is a week from today, October 3.

At the Dagstuhl open problem session last week I gave the following conjecture that I had worked on with Harry Buhrman and Rahul Santhanam the week before in Amsterdam.

(*) NEXP is not contained in NP/n^c for any constant c.

NEXP is the class of languages computable in nondeterministic time 2^poly(n), NP is nondeterministic polynomial time and n^c represents advice, non-uniform information of up to n^c bits that depend only on the input length. No one would think (*) is false, the question was to prove it without using any assumptions.

I described the failed approach using derandomization via IKW. I also mentioned the best known separation, that NEXP is provably not in NP/n^o(1).

Later someone asked me how to prove that known result. I tried to reconstruct the proof on the fly. I ended up with a proof that also showed (*) and didn't use any derandomization.

What's the lesson? Sometimes a proof shows up in the strangest places, like when accidentally proving something stronger when you meant to prove something weaker.

Proof of (*): Assume (*) false. NE (the class of problems computable in nondeterministic time 2^O(n)) would be in NTIME(n^k)/n^c for some k since NE has linear-time complete sets. We now have EXP is in NEXP is in NP/n^c is in NE/n^c is in NTIME(n^ck)/n^c2 (by translation) in DTIME(2^nck)/n^c2. From this you can use standard diagonalization to get a contradiction.

Later Harry, Rahul and I strengthened the result to show

NEXP is not contained in P^NP[nc]/n^c for any constant c. (That's polynomial time with n^c queries to some NP-complete set and n^c bits of advice.)

The proofs relativize and you can't do better with the size of the advice or number of queries with a relativizable proof.

Markets and Polls

A couple of weeks ago a strange thing happened on our electoral markets map. California turned red for a couple of hours. A few days later Michigan turned red as well. Neither of these states are about to vote republican, rather there were odd trades of Obama at a very low price in California and McCain at a high price in Michigan. Since we used the closing price the states were colored wrong until another trade occured.

So we adjusted our algorithm so that if the closing price is lower than the bid price (the price someone is willing to pay) we use the bid price instead. Also if the closing price is higher than the ask price (the price someone is willing to sell) we use the ask price. That seems to avoid the problems of rouge trades.

Which brings me to a controversial post at fivethirtyeight.com, a site that makes predictions based on poll numbers. Nate Silver notes that the prediction of Obama of the markets to win the presidency (about 58%) is much lower than his site's prediction (about 72%). Silver suggests the disparity is because of a rouge trader or traders that seem to be driving the price down and even buying Hillary stock.

I don't buy it. There is quite a bit of volume on these securities and the prices on Obama should bounce back quickly and in fact it does. The rouge trader cannot explain a difference of 14 points. The Hillary factor can be explained by the long-shot bias (people overweigh low probability events). The markets suggest that the probability that Hillary is president is about the same as McCain winning Illinois which sounds about right (even if they are both too high at around 4%).

I have a different theory: The race is tighter than the Silver analysis suggests. The polls can give you numbers about each state but not the correlation between them. Silver gives an explanation of how he handles the correlations in his simulations:

Our simulation accounts for this tendency by applying a similarity matrix, which evaluates the demographic relationships between different states by of a nearest-neighbor analysis as described here. Our process recognizes, for instance, that as the polling in Ohio moves, the polling in a similar state like Michigan is liable to move in the same direction. On the other hand, there may be little relationship between the polling movement in Ohio and that in a dissimilar state like New Mexico.

Silver admits he has little data to back up this claim. I believe the correlations are much tighter—that most of the states might move in the same direction depending on some future event or ad or gaffe or performance on the yet-to-be-held debates, that there is high future correlation even between Ohio and New Mexico.

The swing states are typically highly correlated and if the four states running about 50% (Nevada, Ohio, Virginia and New Hampshire) all go to McCain then the Electoral college ties and it would just take one other state (like New Mexico) to push it over.

The analysis of each state can be done well with polls and historical data and the market prices and polls for the individual states do not differ that much. But understanding the correlations between states is more guesswork and I trust the wisdom of the crowds over the wisdom of the one.

How well do Academic Books Sell?

(Thanks to Harry Lewis for help on this post.)

What kind of academic books sell well and which ones do not? This depends on how you define academic, book and well. Even so, I have one authors data points to share. My advisor Harry Lewis has written several books of very different types and was kind enough to share his numbers and some comments with me.

1. Unsolvable Clases of Quantificational Formulas 1979. A monograph on an extremely specialized topic. He says I don't know how many it sold, but if it sold 1000 it means my mother bought 500.
2. Elements of the Theory of Computation (with Papadimitriou). Textbook in Automata Theory. 1981. First edition sold 38,000, second sold 19,000. I'm surprised how well it sold- its a fine book, but there are lots of books on automata theory out there. Of course, there were fewer in 1981. Also, the used book market was not as efficient then as it is now.
3. An Introduction to Computer Programming and Data Structures using MACRO-11 1981. 4000 copies. Specialized, not surprising. And clearly irrelevant now.
4. Data Structures and their algorithms (with Larry Denenberg). 1991. 5000 copies. He says Disapointing, we worked very hard on that one. By 1991 there were already quite a few books on the market. And CLR, which is both broader and superb, began to dominate the market.
5. Excellence Without a Soul: How a great university forgot Education. 2007. Sold 13,000. Very happy with that- books like this usually sell about 3000-5000. AND there is a paperback version coming out now.
6. Blown to Bits: Your Life, Libery, and Happiness After the Digital Explostion (with Hal Abelson and Ken Ledeen) He says: Also a trade book. Just appeared June 15, but seems to have sold 3000 in the first two weeks. People like it, it is even sold in some airports, but there haven't been any newspapers reviews and there have been few online reviews too, so its been hard to attract a lot of notice. I'll review it in my column and on my blog soon. Need to finish it first!

Another Year, Another Genius

The recipients of the 2008 MacArthur Genius Awards include yet another member of our broad community, Alexei Kitaev a quantum computing star at Caltech. Congratulations!

The Communication Complexity of MAX: Open problem

Alice has x, an n-bit integer. Bob yas y, an n-bit integer. They want to both know, max(x,y). This can be done with n + \sqrt{2n} + O(1) bits of communication.

1. Alice sends the first \sqrt{2n} bits of x.
2. If Bob can deduce that x LESS THAN y then he sends 11y and they are DONE. If Bob can deduce that x GREATER THAN y then he sends 10, Alice sends the rest of x, and they are done. If the first \sqrt{2n} bits of x and y are the same then Bob sends 0.
3. (This step is reached only if x and y agree on the first \sqrt{2n} bits.) Alice sends the next \sqrt{2n}-1 bits of x. If Bob can deduce that x LESS THAN y then he sends 11 followed by all BUT the first \sqrt{2n} bits of y (which Alice already knows since they are the same as hers) and they are DONE. If Bob can deduce that x GREATER THAN y then he sends 10, Alice sends the rest of x, and they are done. If the first \sqrt{2n} bits of x and y are the same then Bob sends 0.
4. (sketch) In the ith round, if there is one, Alice sends \sqrt{2n} - i bits.

We leave the analysis that this takes n+\sqrt{2n}+O(1) bits to the reader.

It is easy to show that the max(x,y) problem requires n bits of communication (also left to the reader). So we have

1. Upper bound of n+\sqrt{2n} +O(1).
2. Lower bound of n.

Open Problems

1. Close this gap! Or at least get a larger lower bound or a smaller upper bound.
2. The protocol above is similar to the following problem: Assume there is a building is n stories high and there is some floor f such that, dropping an egg off of floor f it will break, but off of floor f-1 it will not. If you have 2 eggs, how many egg-dropping do you need to determine f? (NOTE- if an egg breaks you cannot reuse it.) For 2 egges you can do this with \sqrt{2n}+O(1) egg-droppings (and this is tight). For e eggs you can do this with (e!)^1/en^1/e+O(1) droppings (and this is tight). See this paper for writeups of these results. (NOTE: I am sure this problem is ``well known'' but have not been able to find references. If you know any please comment or email so I can insert them into the writeup.) Is there some communication complexity problem for which the e-egg problem supplies the key to the answer.

Sum-Product Theorems

At a guest talk at COMPLEXITY a few years ago Avi Wigderson gave a great talk on SUM-PRODUCT theorems. The slides are the last item on this page His talk applied SUM-PRODUCT theorems to a variety of places, in both mathematics and theoretical computer science. He mostly used SUM-PRODUCT theorems over finite fields.

This talk inspired me to look up the proof of SUM-PRODUCT theorems over the reals (which are easier), and do a writeup of the best known results, which is here. (It includes references to the theorems stated below.) If you find any typos or thing to fix, let me know (by email- would not make for interesting comments.)

What is a sum-product theorem? Let A be a set of reals.
A+A = { x+y | x,y &isin A}

A TIMES A = { x TIMES y | x,y &isin A}
A SUM-PRODUCT theorem says that they can't both be small. The following is known and is in the order of quality of result (not quite the same as date of PUBLICATION--- note that this is not the same as order of discovery).

1. Erdos and Szemeredi (1983) proved that there exists an &epsilon such that, if A is a set of n integers, then either A+A or A TIMES A is at least &Omega(n^1+&epsilon) (All subsequent results are for A a n reals.)
2. Nathanson (1997) proved &epsilon>1/31.
3. Chen (1999) proved &epsilon>1/20
4. Ford (1998) proved &epsilon>1/15.
5. Elekes (1997) proved &epsilon>1/4. (My writeup includes this result.)
6. Solymosi (2005) proved &epsilon>3/11. (Actually he has a slightly stronger result. My writeup includes the slightly stronger result.)

Dagstuhl Review

This week I'm at a Dagstuhl seminar on Computational Complexity of Discrete Problems, the end of summer trip for me as Northwestern's fall quarter classes start next week. Dagstuhl has changed in subtle ways (we get shampoo now) and there are far fewer computers in the computer room as many people now hide out in their rooms using wifi. There is a robot playing foosball table in the main hall that plays quite a mean game and a great diversion to us all. I do however miss the old Dagstuhl days when we were cut off from the world and all we did was drink and prove theorems and being blissfully unaware that, say, my country's economy is tanking.

A few years ago I discussed the problem of finding duplicates in a stream of numbers. Jaikumar Radhakrishnan gave a talk here showing how to find a duplicate in randomized poly-log space using only one pass through the data.

Also parallel repetition is making quite a comeback because of its connections to PCPs and the unique game conjecture. Raz recently showed limitations on parallel repetition, basically the error goes down at least quadratically as bad as you like. Thomas Holenstein talked about his proof that gives cubically as bad and Oded Regev talked about the general connections between unique games, parallel repetition and semidefinite programming relaxations.

These were just a taste of the interesting stuff discussed this week. Talks, abstracts, slides and more here.

Opening up the ACM Digital Library

(Guest Post by Kamal Jain)

Opening Up the ACM Digital Library: An Alternate Method of Payment for the ACM Portal

The primary objective of the ACM digital library (ACM DL) is to make ACM scientific content accessible. It is currently funded by various methods including subscription fees and some commercial deals, such as referral business. The subscription fee hinders broad access of the content. I've been thinking about how we can make the portal freely available. If the ACM DL is free and open, our scientific research will make more of a contribution to society and human well-being, the first moral imperative listed in the ACM Code of Ethics. Consider the contribution of Wikipedia to our society based on its being free and open.

Whether we could achieve an open ACM portal and other scientific content lies in the subject of Creative capitalism. It is a complex subject and one can perhaps write a dissertation on it with a chapter on free access to social content, i.e., the content whose primary goal is to benefit the society. I have a longer post on this topic, focusing on the opportunity to open up the ACM portal. The paper avoids technical complexity and is easy to follow.

Feel free to give feedback in the comment section of this blog. If you prefer you may also drop an email to me (firstname_lastinitial @ microsoft.com).

Fringe Science

We caught the season premiere of Fringe over the weekend. The opening credits have words describing the "Fringe Science" topics the show will deal with such as Teleportation, Precognition, Nanotechnology and Artificial Intelligence. I half expected to see Quantum Computing on the list.

The movie had various stock science characters, the crazy professor locked in an insane asylum for the last 17 years and his son, who once lied about his credentials to be a chemistry professor and managed to get a few papers published before he was caught.

The son said at one point the father would have to solve "mixed integer programs" for his conscious sharing process. When I hear mixed integers I think of odds and evens living side-by-side in perfect harmony.

But after some Googling, turns out Mixed Integer Programming is a variation of linear programming where some of the variables are constrained to be integers and even has its own workshop MIP. MIP generalizes integer programming and is thus NP-complete. So the take-away message from Fringe is

You need to prove P=NP to communicate with the dead.

Some New Lower Bounds on actual VDW numbers

Tamara Giorgadze, a ninth grade student at McLean High School (in Virginia) has obtained some NEW lower bounds on some VDW numbers: See this website

This is excellent work! I was not her mentor, Hunter Monroe was. (He has done some work in Complexity on whether there are natural problems with speedup, though his day job is as an Economist.)

Yahoo more popular than Google according to Google

What phrase when typed into google returns the most hits? I have some data here (may have changed by now) that I got just by googling things that seemed promising. If you can find a phrase that returns more hits than those listed here, in their categories, then leave a comment about it.

Any phrase that gets over 10,000,000,000.

1. www: 25,670,000,000
2. a: 20,080,000,000
3. the: 17,040,000,000
4. and: 14,420,000,000
5. i: 10,100,000,000

Real words that get over 500,000,000.

1. yahoo: 2,920,000,000
2. google: 2,710,000,000
3. english: 2,480,000,000
4. sex: 851,000,000

Famous People that get over 85,000,000. (Perhaps we can define famous by some cutoff.)

1. Washington: 550,000,000 (Cheating: has multiple meanings.)
2. Jesus: 260,000,000
3. Lincoln: 212,000,000
4. Beatles: 88,200,000 (They once said they were more popular than Jesus". Not according to google.)

Words associated to Religions that get over 100,000,000.

1. God: 677,000,000
2. Christian: 507,000,000
3. Bible: 183,000,000
4. Islam: 147,000,000
5. Catholic: 126,000,000

Common Names that get over 100,000,000.

1. Smith: 456,000,000
2. Jones: 327,000,000

Another Dutch Defense

Yesterday I attended my fifth Dutch thesis defense. The Dutch defense is unlike most any other country with a formal ceremony much like an American wedding. I wrote a detailed description of the Dutch defense when I attended Hein Röhrig's defense in 2004. This year I marched as a full professor but not as an actual opponent. I just really enjoy the ritual so lacking in American defenses.

The defender this time around was Steven de Rooij, a student of Paul Vitányi and Peter Grünwald. Peter specializes in learning theory and Paul, of course, studies and co-wrote the book on Kolmogorov complexity, an algorithmic measure of information and randomness. True to form Steven's thesis brought together both areas in some exciting ways. His thesis Minimum Description Length Model Selection looks at the formalization of Occam's razor that a model with the shortest description consistent with the data is typically a good one. Steven examines several models with an eye toward accuracy and practicality.

In a few weeks I start teaching a course on Kolmogorov complexity at Northwestern, a course I've taught quite successfully a couple of times at Chicago. The idea is so simple: the amount of information or randomness in a string is the size of the smallest program that generates that string. This simple idea leads to a rich theory with some very neat applications and is just one of my favorite topics.

SODA 2008 accepted papers list is out!

(Posted by request from Claire Mathieu.)

SODA'09 list of accepted papers is now available. The list also includes abstracts of the papers.

1. Abstracts of the paper! This is great- I hope FOCS, STOC, COMPLEXITY, and OTHERS do that in the future. Makes it easier to tell if I want to download the paper ahead of time.
2. Authors who got in CONGRADS!
3. Authors who got in: make your conference version well written. Make sure that the casual reader knows what you did from the intro. Hilow complete do the proofs have to be? If you don't plan on writing a journal version (shame on you?) then make sure the proofs really are complete.
4. If the conference version has complete proofs then is it worth getting out a journal version? In one sense you are supposed to since it gets refereed. Also, most Schools count journals more than conferences for promotion. But does refereeing really help? See this and other essay by Dr. Z for some interesting opinions.
5. SODA has parallel Sessions. What are natural splits? Do people working on Approx algorithms not go to talks by people working on Randomized algorithms? I doubt that. Readers: what are your ideas on how to do parallel sessons? For SODA and in general.
6. How many members of the COMPLEXITY community go to SODA? How many members of the SODA community to to COMPLEXITY? How can we define this question? We could see how many people who have been to 3 of the last 6 of conference X go to conference Y. I would guess that more COMPLEXITY people go to SODA then SODA people go to COMPLEXITY.

Jogging on Trips

I took up jogging by necessity. My doctor told me I needed more exercise and when I moved to Amsterdam in '96 there were no real health clubs to be found in the nearby suburb where we lived. The biking paths made excellent jogging paths and so I picked up the sport.

Now I am back in Amsterdam and had a nice run this morning along one of the main canals. The bike paths had more bikes than I remembered but I managed to avoid any major accidents.

I love taking a run when I travel. Most cities are located near water and you can usually find a nice long flat path along rivers or lakes. I've jogged along the Danube in Ulm and Vienna. The most beautiful was along the Pacific in Kaikoura, New Zealand and for the other extreme: Stuttgart. I can't always find a path—Hong Kong has too many hills and docks.

Jogging gives you a chance to see the city, it helps with jet lag, and I feel a bit better after it ends. If only running wasn't so time consuming and so much work.

Chicago is no exception with beautiful paths along Lake Michigan from Hyde Park (home of U. Chicago) up to the North end of the city. Come, run and enjoy.

Three sequences

Here are three finite sequences. There is no next element, I give you the complete sequence. What rule did I use to form these sequences?

1. 8,5,4,9,1,7,6,3,2
2. 8,5,1,4,9,2,7,6,3
3. a,i,s,e,t,d,m,c,o,l,p,n,x,v,b,w,y,f,r,u,k,g,z,h,j,q

Tracking Trends in Computer Science

What are the trends in computer science? This is a hard question to quantify; however, Brighten Godfrey has given it a shot on his blog here: trends. He counts how often certain words appear. What other ways could one measure this? ~

Announcements

The FOCS conference is coming up October 25-28 in Philly. Early conference and hotel registration by October 3.

The STACS conference submission deadline is September 15.

Some Theory Funding News from the Committee for the Advancement of Theoretical Computer Science. Take advantage of the current theory-friendly environment at the NSF while it lasts. If you were putting together a letter of intent for CDI, stop and read this.

Luca reports on the untimely passing of probabilist Oded Schramm.

I'm traveling the next two weeks to two of my favorite European haunts, CWI in Amsterdam and Dagstuhl. I'll keep blogging from the other side of the pond.

I would bet on INTRADE that INTRADE will do badly picking VP Nominations

(Lance and I independently made a post on VP selection. This post is not related to his, nor is his related to mine. Dave Barrington helped me with some of the history in this post, as did some folks in their 80's who assure me that Nixon was a surprise VP pick.)

The day before McCain picked Palin a pundit said the following: I don't know who it will be but INTRADE has had a big spike for Romney. INTRADE is always right, hence I predict that some insiders know that its Romney and that is who it will be

Well, INTRADE is not always right, even before the Palin Pick. And would an insider be guilty of insider trading? I predict that in the future VP will be one of those things INTRADE does badly on. Why? Because it is idiosyncratic. Picking the Prez Nominees is like picking the Oscar: small number of possibilities, and one has a sense of things. Picking the VP is like picking what movie Lance Fortnow favorite movie of 2008: too many possibilities, too ill defined (what if he saw a movie made in 1998 in the years 2008, does that count?) and too dependent on his mood.

In the past there was no INTRADE, but there was a short list of VPs. Below is a list of VP candidates (not including incumbents VPs) and whether I think they would have done well on INTRADE. My speculation is based mostly on if they would have been on the short list. I also include the Prez Candidate, the party, and WON/LOST. BADLY means would do badly on INTRADE. GOODLY means would do goodly on INTRADE. OKAY is inbetween.

1. 2008: McCain picks Palin. Rep. BADLY.
2. 2008: Obama picks Biden. Dem. GOODLY.
3. 2004: Kerry picks Edwards. Dem. GOODLY. LOST
4. 2000: Gore picks Lieberman. Dem. OKAY. LOST
5. 2000: Bush picks Cheney. Rep. BADLY. (Cheney was head of VP selection committee, so really Cheney picked Cheney.) WON.
6. 1996: Dole picks Kemp. Rep. BADLY. LOST
7. 1992: Clinton picks Gore. Dem. OKAY. WON
8. 1988: Bush picks Quayle. Rep. BADLY. WON
9. 1988: Dukakis picks Bentson. Dem. OKAY. LOST
10. 1984: Mondale picks Ferraro. Dem. BADLY. LOST
11. 1980: Regean picks Bush. Rep. GOODLY. WON
12. 1976: Ford picks Dole. Rep. OKAY. LOST
13. 1976: Carter picks Mondale. Dem. OKAY. WON
14. 1972: McGovern picks Eagleton/Shriver. Dem. BADLY. LOST
15. 1968: Nixon picks Agnew. Rep. BADLY. WON
16. 1968: Humphrey picks Muskie. Dem. GOODLY. LOST
17. 1964: Goldwater picks Miller. Rep. BADLY. (Miller was in House not senate, so a surprise.) LOST
18. 1960: Kennedy picks Johnson. Dem. GOODLY. WON
19. 1956: Stevnson picks Kefauver. Dem. GOODLY. LOST. (Was serious contender for nomination.)
20. 1952: Stevenson picks Sparkman. Dem. BADLY. Speculation- (Was not a contender for nomination.) LOST
21. 1952: Eisenhower picks Nixon. BADLY. He was a 39 years old unknown at the time and a surprise. WON

1. 10 BADLY, 8 GOODLY, 5 OKAY. INTRADE usually does much better than this.
2. Dems: 6 GOODLY, 3 OKAY, 3 BADLY.
3. Reps: 1 GOODLY, 1 OKAY, 6 BADLY.
4. WINNERS: 2 GOODLY, 2 OKAY, 4 BADLY.
5. LOSERS: 3 GOODLY, 3 OKAY, 5 BADLY.

The winners/losers things may be unfair since these were all non-incumbents; however, some of the incumbents lost (Bush-Quayle and Carter-Mondale) so I leave it be. The stat I find most interesting is that INTRADE doesn't do that well here. Or wouldn't have. I may return to this study 10 years from now when I have real INTRADE data.

The Big Aggregators

Friday morning I wanted to know where the rumors were pointing to for McCain's running mate selection. I could have searched various political blogs, but instead I went to Intrade and checked out the current prices on VP candidates. Since Intrade has constant trading, these prices do aggregate the various rumors and their veracity. Sarah Palin was running at about 60%. Apparantly I was not the only one with this idea has Intrade had major performance problems on Friday.

After seeing the price for Palin, I had a question many other Americans were asking: Who is Sarah Palin? So I went to that other great aggregator Wikipedia and read up on her. The scariest part: For the first time, someone on a major party ticket is younger than me.

The wisdom of crowds boiled down to a number on a trading site and a constantly updated page with much more than I need to know. The rest of the Internet is just commentary.

Some graphs of Intrade's market on the Palin market lifetime and in the last day.

Two things to note: The markets didn't predict Palin until close to the end. Also big volatility in the closing hours. Market aggregate public information—they don't predict what isn't out there. In the last hours, even little rumors, accurate or inaccurate, can drive prices as some people try to make a fast buck.

Chris Maase's blog as always has much more Palin and all other things about prediction markets. Also check out the new Intrade.net which now has do it yourself prediction markets.

I created a simple widget for our Electoral Markets Map. You can see in on the left sidebar until the election and always have the most up to date account of who's ahead state by state.