Academic Dominance

Maureen Dowd's column yesterday mentioned that Obama was being accused of reading a book about the end of America written by a "fellow" Muslim. Turns out I read the same book, Fareed Zakaria's The Post-American World.

Not so much about the end of America, but the gradual ending of America's economic dominance in the world. Zakaria contrasts America today with the rise and fall of the British empire. The book focuses on China and India, their recent rise and the challenges each faces, as well as suggestions for America to keep their competitive edge.

At the University level, Zakaria seems quite bullish on America especially in CS.

The situation in the sciences is particularly striking. A list of where the world's 1000 best computer scientists were educated shows that the top ten schools are all American. US spending on R&D remains higher than Europe's, and its collaborations between business and education institutions are unmatched anywhere in the world. American remains by far the most attractive destination for students taking 30 percent of the total number of foreign students globally. All these advantages will not be erased easily, because the structure of European and Japanese university—mostly state-run bureaucracies—is unlikely to change. And while China and India are opening new institutions, it is not that easy to create a world-class university out of whole cloth in a few decades. Here's a statistic about engineers that you might not have heard. In India, universities graduate between 35 and 50 Ph.D.'s in computer science each year; in America, the figure is 1,000.

We have seen some countries like Israel create world-class universities out of whole cloth in a few decades. The US did it themselves in the late 19th century. So China and India could have dramatical success at the university level if they make the commitment to resources and change. Until recently the Indians and Chinese have come in large numbers to our graduate programs and have just stayed in the US. Now, for may reasons not the least of which is the improving economic conditions in both countries, we are seeing more researchers heading back to their native countries whether it be Turing Award winner Andy Yao or just a large number of Indian scientists that are moving or plan to move back to India. Imagine the changes we've seen at Israeli universities in a country with a 10-digit population size.

Weird Sum/ith largest/Wallet-- revisited

1. In Richard Matthew McCutchen's Guest post he challenged the readers to figure out a certain sum. And I challenged them to help me do a better pi in html.
   1. KKMD (comment 3) is correct, it is the largest prime that divides n. The formal proof is here.
   2. pi: I originally used an & followed by pi which yields &pi
   3. pi: I was supposed to use & followed by pi and then a semicolon which yields π
   4. pi: Lance says to use < span style=" font-family:times" > & pi;</span> which yields π
2. Some of the comments from the posting on ith largest of n inspire some random thoughts from me:
   1. Why on earth would anyone be doing a computer search for such algorithms? (for algorithms to find ith largest of n with as few comparisons as possible). One hope is that with enough empiricial evidence we may get EXACT values for how many comparisons it takes. Also, for the challenge! But YES, limited practical value. But see next point.
   2. Why do you think your conjecture is true? The known algorithms for finding ith largest of n take n+(i-1)log n + O(1) and begin by making comparisons pairwise. For i small this is optimal up to the O(1). So in this realm it seems likely. But what is `i small'? When finding the 10th largest out of 40 is that more like i small or like you are finding the n/4th largest element? Don't know- want to find out. Another reason to do this- when is small small?
   3. A commenter says there is interesting info in a Tech Report that may be hard to find. The notion of a Tech Report that is hard to find may be unfamiliar to young people. With the web it may be easier to find some unpublished papers then some published ones, depending on who the authors are and the journals are. (If someone knows where the Journal version of Barrington's paper on Bounded Width BP containing NC¹ is online please let me know. Barrington does not have it on his website or know where it is online.)
3. Lance recently recommended a certain wallet in this blog. On his advice I bought it and its great. What I wonder is, how big a mover and shaker is Lance? Should they have given him a free wallet since he influences others? How many others have bought it based on his recommendation? At Maryland Theory Day there was a talk about how sellers should give people of influence discounts since they will influence others to buy their product. This is not a new idea, but with modern technology it can be better targeted.

World Series at FOCS

The timing of the FOCS conference in late October often overlaps with the World Series and on rare occasions they happen in the same city at the same time. Checking back through the 48 previous FOCS only once before in 1997 FOCS was in Miami Beach October 19-22 with Game 2 of the world series October 19th with the Florida Marlins losing to Cleveland at Pro Player Stadium in Miami.

A couple of other close calls. In 1992, I had tickets to a potential series in Pittsburgh but I've told that sad story before. In 1999, FOCS was held in New York October 17-19 and the Yankees hosted Atlanta a week later in the series. Last year FOCS was held in Providence October 20-23 and just a short drive up I-95 the Red Sox beat the Rockies twice October 24-25.

This year we have a perfect overlap. The 2008 FOCS Conference runs October 25-28 in downtown Philadephia and Games 3, 4 and 5 (if necessary) of the Series between the Phillies and the Tampa Bay Rays will be held October 25-27 three miles south in Citizens Bank Park.

But I'll miss the fun and won't make FOCS this year. I'd love to hear from any FOCS attendee that manages to snag World Series tickets and gets to enjoy the two great fall classics.

An interesting Summation

(Guest post by Richard Matthew McCutchen.)

The formula below appears in The TeXbook as a typesetting exercise (I have slightly modified it): The expression has a clever mathematical meaning that is not discussed in the book. Try to find it and prove it!

Let p(n) be the limit as m &rarr &infin, m &isin Z, of

&sum_k=0...&infin (1- cos^{2m}(k!ⁿπ/n))

(Comment from Bill: &pi is supposed to be pi, the ratio of circumference to diameter of a circle. html doesn't really do a good pi- if someone knows how to, in html, do a better one- let me know.)

Finding the ith largest of n numbers for i,n SMALL

Exactly how many comparisons does it take to find the i^th largest of n numbers? For i=1 and i=2 these numbers are known exactly. Beyond that I'm not sure, though I do know that we don't know (say) how many comparisons to find the 15th largest element out of 30. (There is a table in KNUTH, but I could not find a website of these things. If someone knows one, please comment.)

The following conjecture, if true, would help speed up computer searches for such algorithms and may lead to interesting math in and of itself. Let V(i,n) be the min number of comparisons (worst case) to find the i^th largest of n numbers.

Conjecture: There is an algorithm for finding the i^th of n numbers that uses V(i,n) comparisons that begins by comparing x₁ to x₂, x₃ to x₄, x₅ to x₆, ..., x_n-1 to x_n (if n is even, else end at x_n-2 to x_n-1).

A weaker conjecture may be more tractable, where we allow V(i,n) + 1 or + some constant.

How Much is a Proof?

Back in our grad schools days, Noam Nisan told me he preferred incomplete proof write-ups in papers. By being forced to fill in the missing steps, he could really understand what was going on in the proof.

I don't agree with Noam. I shouldn't have to struggle to figure out how the author went from point A to point B. I've spent far too many hours trying to understand the logical jump when the author says ``Clearly'' or ``Obviously''. On the other hand I don't want the authors to spell out every small algebraic manipulation either. And it's just completely infeasible to give a fully formal logical proof of even the simplest theorems.

So what level of proof should one give? As a general rule you should write for the reader. What would make it easier for him or her to understand your paper? When you leave out some details are you doing that because it would clutter your proof or because you are trying to save yourself some time. If it is the latter you do no one any favors.

Don't make assumptions of your readers. If you use a supposedly ``well-known'' technique, then either spell it out or make it clear what you are doing with a reference for those of us unfamilar with such techniques.

And how many times have you read ``the full details will appear in the final version'' where there are no later versions? Put those details in now. If you hit a proceedings page limit, have a full paper on the web with a footnote in the conference version pointing there.

If you do have a technically messy proof, the technicalities often overshadow the very pretty new ideas you needed for the proof. Be sure to also give a proof sketch that brings those ideas to light.

But mostly the Golden rule applies—Write your proofs as you would like others to write proofs for you.

Theory Day at University of Maryland

University of Maryland had its 20th THEORY DAY. It was organized by Samir Khuller Samir Khuller and Azarakhsh Malekian.

1. There was a theme! All of the talks were on Game Theory/Social Networks/Auctions/Internet stuff. Most theory days do not have a theme, but this one was organized in a different way- Azar knew that some of these people would be in town for INFORMS.
2. Having a theme was GOOD. Usually at theory day (anywhere) I have to get my head into a certain mode of thinking and then it changes with every talk. Here my head was in the same mode all day.
3. One odd thing- I got 4 `short introductions to Game Theory'.
4. Jason Hartline and Nicole Immorlica gave talks. I had never met them before so I got to see if they looked like their images in the this famous poster. They looked more like themselves then Lance did, but not much. Then Jason turned his back and bent it a bit and THEN he looked like the poster.
5. Here are the talks:
   1. Mohammad Mahdian. Yahoo! Research. Externalities in Online Advertising.
   2. Nicole Immorlica. Northwestern University. The Role of Compatibility in Technology Diffusion on Social Networks.
   3. Konstantinos Daskalakis. Microsoft Research. Computing Equilibria in Large Games.
   4. Jason Hartline. Northwestern University.
   5. Vahab Mirrokni. Google. Submodular Optimization: Maximization, Learning, and Applications.
   6. Amin Saberi. Stanford University. Game Dynamics, Equilibrium Selection and Network Structure.
6. They all gave excellent talks. Why was that? Well, for one thing, they were excellent speakers. But also this is a relatively young field so the work is still close to the motivation (there are fields of math where the motivation has been forgotten over time!). And the motivation is itself easy to explain.
7. The conference was intentionally the same time as INFORMS so that people who were going there anyway could give talks and/or attend our Theory Day.
8. Kudos to Samir and Azar for organizing it!

The Fiscal Crisis

Sitting in our Ivory Towers, our day-to-day lives don't change much even when dramatic events happen in the "real world." Even with the current economic crisis my basic job of teaching and research much go along as they have before. Whether P = NP does not depend on the GDP (though the converse might be false).

But in the end it does all come down to money. University endowments have shrunk. Alumni donations will surely drop. Less tax revenues will hurt government support of public universities. Industrial research labs may also take a hit if their corporate parents have financial difficulties.

Schools like Northwestern have structured their finances so they can weather short term shocks in the economy but a prolonged recession or depression will start to take its toll.

New faculty hiring will likely be the first victim in universities. Tenured professors may delay their retirement after taking a hit in their CREF accounts holding up slots for new hires. Unversities worried about their long-term finances may also slow down opening up new positions.

On the other hand we should see increased enrollments on every level which may push the need to hire more CS faculty. Computer Science has lost its lustre in recent years, but still reliably produces jobs and there is a flight to safe majors in times of economic turmoil.

People who have trouble finding a good job often go back and get their Master's while they wait out the recession. We should also get more people interested in Ph.D.s as alternatives dry up. My sources told me we have seen a major drop in Indian IIT graduates going on to Ph.D.s because banks have offered them high salaried positions. With the banking industry taking the biggest hit, we welcome those IITers back to academics.

Finally in every crisis, we look for someone to blame, and some blame the algorithms.

Somehow the genius quants – the best and brightest geeks Wall Street firms could buy – fed $1 trillion in subprime mortgage debt into their supercomputers, added some derivatives, massaged the arrangements with computer algorithms and – poof! – created $62 trillion in imaginary wealth. It's not much of a stretch to imagine that all of that imaginary wealth is locked up somewhere inside the computers, and that we humans, led by the silverback males of the financial world, Ben Bernanke and Henry Paulson, are frantically beseeching the monolith for answers. Or maybe we are lost in space, with Dave the astronaut pleading, "Open the bank vault doors, Hal."

Thanks for better upper bound. Still want better lower bound- On Comm Comp of MAX

I posted on the max problem a while back.

Alice has x, an n-bit integer. Bob has y, an n-bit integer. They want to both know, max(x,y). This can be done with a deterministic n + \sqrt{2n} + O(1) bits. Can they do better?

Anon Comment 5 on that post, and possibly a paper that was pointed to, lead to a Deterministic Protocols that took n+O(log(n)) bits. I am presenting it carefully in this post, hoping that someone will NOW prove the lower bound OR get an even better upper bound.

When I had the upper bound of n +\sqrt{2n} + O(1) I thought it was optimal. Now that I have the upper bound of n+O(log n) + O(1) I'm not so sure. This is a good example of why lower bounds are so interesting- someone clever may come along with a better algorithm-- How to you prove that they can't?

1. Alice has x, Bob has y. L is a paramter to be determined later. We will assume L divides n. Let m=L/n. Alice views x as x₁...x_m where each x_i is length L. Bob views y as y₁...y_m where each y_i is length L.
2. Alice sends to Bob a string A of length L that is NOT any of x₁,...,x_m. Bob sends Alice a string B of length L that is NOT any of y₁,...,y_m. Note: we will need 2^L > n/L.
3. So long as it looks like the strings are identical They alternate sending the next block: Alice sends x₁, Bob sends y₂ Alice sends x₃, Bob sents y₄ (NOTE- nobody has to send a bit saying `we are tied'.) They keep doing this until one of them notices that the strings are NOT equal. If they they never discover this then they spend n+Lb bits and discover x=y. They both know max since its x=y.
4. If Bob notices that x_i > y_i then he will send B0. Alice knows that B can't be one of Bob's segments, so she knows why Bob send this. She will then send the rest of her string that she has not already send. They both know max(x,y). This took n+3L bits.
5. If Bob notices that x_i < y_i then he will send B1. Alice knows that B can't be one of Bob's segments, so she knows why Bob send this. Bob will then send the rest of his string. They both know max(x,y). This took n+4L bits.

What can L be? we needed 2^L > L/n. L=lg n works. So this works in n+4lg n. You can do slightly better by taking L=lg n - lglg n.

Patents and Copyrights vs Web Traffic (guest Post by Amir Michail)

(Guest post by Amir Michail)

Title: Patents and Copyright vs Web Traffic

Software patents are intended to reward innovation, especially by startups with limited resources. But in today's Web 2.0 world of social sites such as twitter, a service is more useful when it has more users. Even if the implementation contains something that is worthy of a patent, getting such a patent is not particularly important because the service will generally have an overwhelming advantage over its clones in terms of number of users -- new users will generally pick the service with the most users, thus resulting in much more web traffic growth for the original service.

Similarly, one could argue that copyright is unnecessary on the web -- those who copy are unlikely to get anywhere near as much web traffic as the original source. For example, someone may copy posts verbatim from a popular blog, but it is unlikely that he/she will get anywhere near as much traffic. In particular, people already linked to the original source, thus giving it higher PageRank.

Admittedly, there are occasions where things don't work out like this and where patents and/or copyright would have been helpful. Consequently, we could have a law that requires search engines to provide a link back to the original source if any for each search result. This would be done using a completely automated heuristic matching algorithm. In this way, those who copy are even less likely to get anywhere near as much traffic as the original source.

A Victim of the Internet

I come from the perhaps the last generation of those who mainly got their news from newspapers. I could spend a morning enjoying the Sunday paper and I still like to pour over the paper over breakfast. But the newspaper industry has been hard hit from the Internet with much less advertising particularly with classifieds going to places like Craigslist and fewer and fewer people reading the physical paper with young people getting their news from the Internet and the myriad news (and comedy) channels and TV. Newspapers have had to shrink staff and reduce the quantity and quality of their product.

This crisis hit home last week with the redesign of the Chicago Tribune. I understand the need for a paper to freshen up its image and can look beyond the extra color and fluff. But it is what's missing that bothers me. Two sections (Business and Local News) have been merged into the first section with business news more focused on personal finance than business. The Sunday Perspective (The Tribune's version of the Week in Review) has become a 3-page editorial/op-ed. But most dramatically is a significant drop in the coverage of real national and international news.

The Tribune hit its nadir last Saturday. The day after the bailout passed the house and was signed by the president, the front page had only one story—on the dating habits of suburban teens. The bailout story was on page 16.

The Tribune picked an interesting time to have their redesign, a month before the elections and with both Chicago baseball teams about to start their (short-lived) march into the playoffs. Perhaps they felt few would unsubscribe during this time. I went ahead and subscribed to the New York Times (instead of just skimming it online) because I still crave real news with my coffee. I'll get both papers for a while and if the Tribune doesn't recover I may have to say goodbye to my old friend.

Contradictions in Math-bad, in Political Pundits- Standard

(This is not a partisan post. I am using a Republican example since it illustates the point so well.)

In most (all?) serious fields of academia it is not acceptable to directly contradict yourself. No so in the field of political pundits. Karl Rove (and others) recently did this as the following clip illustrates. My question is, why do they get away with it? Some thoughts.

1. I only saw this on The Daily Show. No other media seems to have picked up on it. (Some blogs did.) Karl Rove will not be challenged on this. FOX NEWS will not call him into their office and ask him how he could say contrary things.
2. Rove is only talking to fellow conservatives. Its like Cold Fusion worskhop or a Parapsychology conference or an Intelligent design journal or a Bush Rally- your audience is pre-picked.
3. People think (perhaps correctly) that all pundits do it, so nobody is particularly criticized if they do it. (I've seen this reasoning used to defend negative ads.)
4. If Karl Rove was challenged he might say The Daily Show ran that piece because they are part of the liberal media elite.
5. Most people have not had a course in basic logic to tell them when two statements are clearly contradictory. (Though common sense should suffice.)
6. There is an end justifies the means mentality. If Karl Rove helps get McCain elected, then that is all that matters.
7. Is there any serious field of academia where people can make contrary statements and not be called on it?

Expectation of Expectations

Can we quantitatively judge the effect of a debate on the election? One reasonable approach would look at prediction markets. If the value of the security for Obama to win would greatly increase after the debate in the absense of significant other factors, one could conclude that the debate went well for Obama, or at least that he did better than expected.

Intrade, the Irish real-money prediction markets site, went one further and set up a new security 2ND.DEBATE.OBAMA based on the outcome of tonight's presidential debate. In short,

This contract will be settled according to which Presidential Candidate receives the largest increase in value following the Presidential Debate on Tuesday October 7th. The pre-debate value will be calculated for 2008.PRES.OBAMA and 2008.PRES.McCAIN and then compared with the post-debate value for each of these contracts. This contract will expire at 100 if the value of 2008.PRES.OBAMA increases more than the value of 2008.PRES.McCAIN. This contract will expire at 0 if this is not the case.

A similar security for the VP debate paid off zero as there was a slight bump for McCain suggesting Palin did better than expected.

But there is a flaw in the logic for such a security—The market should already take into account the expectation of the debate. In general for any random variable A, the expectation of the expectation of A is the same as the expectation of A, i.e., E(E(A))=E(A).

So, assuming that these securities represent real probabilities, should the value of 2ND.DEBATE.OBAMA before the debate be 50? Not quite. Suppose that there is a 75% chance that the Obama stock goes up 5 and a 25% chance it drops 15. Then the price of 2ND.DEBATE.OBAMA should be 75%. The price of the security indicates who has the least chance of major downside from the debate. But to think one could use this security to predict how well the debate will go makes little sense.

The press release suggests using this security for real-time debate tracking. The price of 2ND.DEBATE.OBAMA should gyrate dramatically on small changes of 2008.PRES.OBAMA. But one could just derive this directly from 2008.PRES.OBAMA and since the later security has much greater liquidity it will likely give better information.

Chris Masse suggested another explanation.

[Intrade] is trying to induce traders into trading more (so as to get more transaction fees), and this new contract offers more upsides for the traders who will bet right. One could double one's initial investment in a matter of 2 days.

In which case all the power to them.

The Unexpected Hanging Paradox-any seriosu math their?

(20th Maryland TCS Day Tue, Oct 14, 2008 9:30am - 4pm)

The liar paradox is very similar to the serious math of Godel's Incompleteness theorem. Berry's Paradox is very simlar to the serious math of the Kolmogorov function (map x to the length of the shortest description of x) being noncomputable.

Is their any serious math that is similar to the Unexpected Hanging Paradox? Here is the paradox:

A judge tells a condemned man that he will hang on either M, Tu, W, Th, or Friday at 1:00PM And that he will be surprised when it happens. His lawyer tells him not to worry: The hanging can't happen on Friday, since if he is alive by Thursday at 1:01PM then he knows it will be on Friday and hence won't be surprised. However, he also knows he can't be hung on Thursday since Friday is out, so if by Wedensday at 1:01PM he alive he will KNOW that it is Thursday. Hence he won't be surprised. Hence it can't be Thursday. Proceeding like this he reasons that he can't be hung. On Thursday the judge comes with the noose- and the prisoner is surprised.

I'm not asking for a resolution-- it seems to be a significant problem for philosophy-- however, I am asking: Is there some serious math that is similar to this paradox?

A minor but perhaps indicative failure of technology

In Feburary of 2007 needed to look up on Hallmark Channel Website if they had some program changes. They did not have any program changes on the website but they did have a number to call. The subwebsite had the number 1-888-390-7474. I called it and it said:

You have reached viewer services at the Hallmark Channel. In order for us to better serve our viewers, this mailbox is specialized designed to answer most of your questions. If you are having trouble viewing the Hallmark Channel, press 1. For a list of program changes, press 2.

I thought GREAT!. I pressed 2.

The following changes have been made to our program scheduled as of Wedensday June 29, 2005. Jane Doe-The Harder they Fall, originally scheduled to air Friday July 1, 2005 9:00 Eastern and Pacific, 8:00PM Central, and 7:00PM Mountain time, has been replaced by Matlock-The Power Brokers.

They had not updated their phone message in two years. I left a message (If you would like to leave a comment, press 4) telling them of their error. I have since called on April 1, May 1, and June 1 of 2007 to see if they have corrected it. They had not. I've also emailed them, to no effect. (Its been fixed since then.)

How could a phone line be this out of date? How could the website maintainers not know this?

1. They got careless and are not suffering for it so they don't know they got careless. I'm not going to stop watching their shows because their website gives a phone number that is two years out of date.
2. Lack of coordination- the right hand does not that the left hand stopped working two years ago.

For this particular issue, the breakdown of technology is not important. But it troubles me that in other domains it might be.

Go Sox

After beating three different teams in three days to make the playoffs, my White Sox join the Cubs in an historic time in Chicago: The first time both Chicago baseball teams are in the postseason since that great 1906 World Series. The Sox open the playoffs today against the surprising AL East winner Tampa Bay.

With the Boston Red Sox that makes all three teams that I have once held season tickets (I lived walking distance from Wrigley for a year and I organized season tickets for the theory group at MIT as a student there). And add on Milwaukee a team I have grown to like as they play in new stadium that I can get to easier than either of the Chicago ball fields and you can't beat the sausage race. And four more teams that hopefully will all be eliminated in the first round. This is just the ultimate playoff year to keep me distracted from various fiscal crises and political activities. I might not get much research done in October.

The eyes of America look at the Cubs who last won a World Series in 1908, one hundred years ago. But although I now teach north of the city, my heart remains with the Southsiders. The best outcome: The White Sox win the world series in five games. Why five and not the full seven? Because it is so much more fun to see the Cubs choke at home.

When does Alice deserve to be a co-author?

When has someone done enough work to deserve a co-authorship? Here are a few scenarios I have seen. I will say what did happen, not what should have happened.

1. Alice comes up with the problem and makes some obvious observations about it, she shows it to others, who solve it. She writes it all up. (Alice got the co-authorship.)
2. Alice comes up with the problem and makes some obvious observations about it, she shows it to others, who solve it. She does not write it up but does some proofreading. (I've seen this twice- once she got the co-author, once not.)
3. Bob shows Alice a problem, Alice makes one observation that is the key. She has put only 2 minutes of work into the paper. (Alice got the co-authorship.)
4. Bob has already written up the 50 page paper and it has covered all of the cases except for one. Alice solves the one case left. It was not a hard case at all. (Alice did not get the co-authorship.)
5. Bob and Carol solve the problem together. Alice is in the room and does not contribute anything, but her tenure case is coming up soon and she is a bit short on papers. (Alice got the co-authorship. This is a rare scenario.)
6. Alice proofreads a paper and finds a serious flaw in it, but fixes tht flaw. It was a rather subtle flaw and needed very clever argument to fix it. (Alice got the co-authorship.)
7. Alice reads Bob's paper and comes up with a generalization that Bob does not care about, but wouldn't really be worth a paper on its own. (The paper did not have the generalization and Alice did not get the co-authorship.)
8. Alice makes a key observation that makes all of the proofs shorter. The Conference version has her as a co-author. However, while writing up the journal version it is noticed that Alice's contribution was not correct. It is removed and the journal version is pretty much what it would have been had Alice not been involved at all. (Alice asked to be taken off of the journal version The other authors were surprised by this and did not mind keeping her as an author. They pointed out that there were other people on the paper that were even less involved. But they agreed to take her off on her insistence.)

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.

The Ultimate Wallet

Once in a while a new product comes along, so well-designed, so cool, that I just have to get one. When I visited Yahoo earlier this month, two separate researchers had independently bought one and I instantly fell in love. I dropped some not so subtle hints to my family who got me one for my birthday and I am now a happy man. I'm talking of the All-Ett, a wallet replacement designed to remain thin even holding my many cards. My back pocket has never been more excited.

The All-Ett solves a problem I shouldn't have. I count 16 plastic cards currently in my wallet and that's only because I make a strong effort to keep the number down. We have the technology for me to hold a single card that can be loaded with the information of all of the other cards. Many universities, including Chicago and Northwestern, now have a single card that serve as ID, libary card, food service and other purposes. But there we have a centralized authority. It would drive the privacy advocates mad, but I'd love a national ID with both a smart chip and RFID and a mechanism that would let any other organization embed needed data on the card.

Why stop there? I shouldn't need a wallet at all. Every piece of plastic or paper in my wallet, including business cards, pictures of my kids and cash, could be handled by my all-purpose cell phone. It wouldn't be difficult to even have it open doors and allow me to start my car so I wouldn't need to carry keys either.

But, alas, those days are far away and I'll need to live with my many cards for a while. At least I have a decent place to store them now.

If a Hobby relates to your work, is it a Hobby?

In yesterdays blog Lance mentions that he didn't see other math people or trade problems when he was on vacation, and that it wouldn't have been a vacation if he had.

This raises a question: Can you ever use a hobby in your work. I give a few examples below.

1. Steve Skiena wrote a book Calculated Bets about mathematical modelling and betting in sports. This combined Steve's lifelong hobby of watching and betting on Jai-Alai with serious math and computer science of interest.
2. Ken Regan's hobby is chess and he has some research there, as seen here.
3. My hobby is collecting novelty songs and I've gotten some blogs out of that. (Is blogging part of my job?) Other bloggers also use their hobbies on their blogs-- Luca and photography comes to mind.
4. Steve Rudich's hobby is magic, and I've seen him entertain at conferences. Some of the magic is based on math.
5. Lance has commented on the show NUMB3RS in the blog, and I wrote a reviewed Season 1 my SIGACT NEWS column. (If I buy the DVD and review it again, is that tax deducbible?)

If your hobby is some game then there may be some math of interest surrounding the game that you could get involved with research on. If your hobby is collecting paintings then you may have a harder time connecting it up with your work. (Maybe Game Theory of Auctions.) Do you even want to connect up your hobby with your work? Hobby is almost defined as not work.

Since most of us (I assume) like math, the line between hobby and work may be hard to see. If I work on Math problems in my leisure time, is that a hobby or work? If one of them inspires a paper then does it cease being a hobby? How does Sudoko fit into this? If I actually use the ZK Sudoko protocol to convince someone that I solved it, is that work or play?

While I Was Gone

Just got back from vacation. Unlike Bill, I didn't see other math people and trade problems with them. Then again it wouldn't have been a vacation if I did.

As reported on a few other theory blogs, computational complexity hit a home run in NSF's new Expeditions Program. A dozen researchers in the New Jersey/New York area won an award for Understanding, Coping with and Benefiting from Intractability. In fact all four of the Expeditions grants has at least some theory connections. I'm not a fan of these big NSF programs but it's good to see the money going to our community.

The September issue of Scientific American focuses on privacy and Anna Lysyanskaya wrote an article on theory-based cryptography. Further Reading points to an old post Zero-Knowledge Sudoku. Thanks for the plug.

Finally Peter Lee writes about the growing theory group at CMU.

What to teach in grad course in Comm Comp- some non-theorists in it

The topic What should a basic graduate complexity course, whose audience is mostly nontheorists (say 15 non-theorists, 20 theorists) have in it has been the subject of a a prior blog. This question is relevant to many people since such courses are common.

Today I ask a question that may be of less relevance. Univ of MD's requirements are such that I will be teaching a course on Communication Complexity that non-theorists will be taking. The Complexity Theory course is not a prereq. I will be using the book Communication Complexity by Kushilevits and Nisan which will add 10 to their book sales this year (maybe less-depends on the used book marked). What should be in such a course? Here is what I am planning, though I am flexible and your answers may influence me.

1. Overall themes: (1) Given a problem, what is its Comm. Comp.? (2) Applications to other models of computation.
2. 2-party Comm Comp
   1. Deterministic: Rectangles, foolings sets. SAMPLE : EQ requires n+1 bits. Not hard to prove, but interesting that, unlike complexity theory, we can actually get real results here. Will look at other functions as well like IP (Inner Product), Not sure if I will do Rank lower bound. Powerful, but somewhat mysterious.
   2. Nondeterministic: covers, relation to deterministic. SAMPLE: NE in N(log n), so in this setting P\ne NP. Also, in this setting NP\cap coNP = P. (P is polylog bits)
   3. Randomized: private coin and public coin. SAMPLE: Randomized provably more powerful than deterministic, as EQ shows.
   4. Relation to Circuits: Lower bounds on monotone circuits for MATCHING and other problems.
   5. Upper and lower bounds on streaming algorithms
   6. Upper and lower bounds on the Cell Probe Model
3. Multiparty Comp Complexity
   1. Multiparty Comp Complexity and Branching Programs and Ramsey Theory Go over Chandra-Furst-Lipton paper on this topic, but fill in all details and background (I'll have my own notes on this.) This is alot of material: Multiparty stuff, Ramsey Theory, Branching Programs. Will also do lower bounds on BP's that use 2-party (these results may imply the results with multiparty, but need to look at it more carefully). Will also do some other material on Branching Programs (might do Dave Barringtons result that NC^1 is in BP_5, but that may take us too far afield).
   2. Other applications of Multiparty comp. Complexity

A nice result, but not good for...

When people ask you if theory is practical you should give them a problem that

1. People actually want to solve.
2. The algorithm and lower bound for it are relevant at reasonable sizes of the input.
3. The algorithm for it can be implemented and perhaps actually has been.

Is there a result that fails on all three? That is, is there a result that

1. People do not care about solving.
2. The best known algorithm/lower bound only apply when the size of the input is astronomical.
3. The algorithm for it cannot be implemented.

I have one in mind. It is from an excellent paper by Alon and Azar: Finding an Approximate Maximum

1. The problem is, given n numbers, find some number in the top half (that is max or 2nd largest or 3rd largest or ... or median). The model is parallel: we get to make n comparisons per round. The question is: How many rounds does it take?
2. Let r(n) be the number of rounds. They proved log^* n - 4 &le r(n) &le log^* n + 2.
3. The algorithm uses a certain type of expander graph. They prove this type exists by prob method, so the proof is nonconstructive.

I like this result alot! I like having very close upper and lower bounds and the proofs are nice. Gives a nice application of a simple type of expander graph! However, I would not use it to convince someone that theory is practical.

Ways Scott could have gotten his question answered

In a blog entry of Scott Aaronson's he asks an interesting question (he often does!) about boy-meets-girl type fiction- both film and literature. Later in comment 20 he asks another interesting question (he often has interesting questions in his comments!):

How could I have gotten efficient answers to my question other than blogging it. I don't know of any existing way to search books and movies by plot-structure other than by querying the the humans who've read or watched them. (Then again, this is probably not a common want.)

Rather than be comment 90 on Scotts blog, I share my thoughts on this question here.

1. Scotts audience is, I assume, mostly CS/Math/Phy people. Not clear if thats really a good target group to ask about literature and film.
2. Is there some other blog which does have the audience helpful to Scott? I honestly don't know, but that is one answer: Find someone who has a blog with a more appropriate audience and ask to guest blog. (And in exchange that blogger can guest blog on Scott's blog and ask about Quantum Complexity.)
3. There used to be READNEWS GROUPS (actually there still are) where there is no head person who controls it, people just post stuff. They are not used so much anymore, but Scott could try to post on an appropriate one. (NOTE: thats how I got some of my Bob Dylan satires, by posting a request to rec.music.dementia)
4. i> Find an expert. I wonder if Google or Google++ or whatever will ever replace asking someone who knows stuff. Scott should just ask Roger Ebert about film. Perhaps for money. Or they could barter since Roger Ebert has always wanted to know about Perfect Completness for QMA. Actually Ebert does have on his webpage a place for people to ask questions; however Scotts question is more complex than the usual How come you recommended movie X when it sucked?-type questions.
5. Are there already experts on the web who will answer questions, either for free or for money or for barter?

Acknowledging anonymous blog comments

Twice times now I have gotten an anonymous comment on this blog that I may want to use in either a paper or my (never-ending) web-monograph on VDW stuff. They are

1. Anonymous posted a combinatorial proof of a summation. See comment 6.
2. Former VDW ugrad posted that the exact bound of polyvdw(x2,3)=29. See comment 11. I asked the obvious people, and they all deny they posted it.

If I use these proofs then I will reference the blog link (how long these links last?) and also give the full proof. I would also like to acknowledge the people who came up with those proofs. How to do this

I would like to thank Anonymous ....

and

I would like to thank Former VDW ugrad...

do not seem like I am really giving them credit. So, what to do? I make the following request:

If you are one of the two people above please email me who you are and which entry you posted.

Will this work? There are two concerns.

1. That nobody will respond.
2. That too many people will respond. How do they verify who they are?

Will this be a bigger problem in the future? If so then future textbooks may have

P vs NP was resolved by kittykat17.

Amihood Amir more famous than Dick Cheney

(Guest post by Richard Beigel.)

Top-9 list of internet fame criteria. You know you are famous when ...

9. You show up on the first page of google hits for your full name (Richard Chang)
8. You take up all 10 slots on the first page of google hits for your full name (Carolyn Gasarch)
7. You show up on the first page of google hits for your last name (Lance Fortnow, Johnny Carson)
6. You take up all 10 slots on the first page of google hits for your last name (Bill Gasarch)
5. You show up on the first page of google hits for your full name ... even when it is misspelled (Richard Beigel)
4. You show up on the first page of google hits for your job title (Richard Cheney)
3*. You show up on the first page of google hits for your first name (Amihood Amir, Don Knuth, Lance Armstrong, Johnny Depp, Johnny Cash)
2*. You show up on the first page of google hits for your initials (Richard M Stallman)
1. You show up on the first page of google hits for your middle initial (George W Bush)

*It was hard deciding which of these two should come first, but Richard Stallman shows up under both and, surprisingly, Don E. Knuth doesn't show up under 2.

Disclaimer: These criteria are intended for the purpose of humor only. They do not represent the opininion of the Natiοnal Science Fοundation or the the Federal Gοvernment, and they will not affect your chances of getting a grant. ~

Olympic Markets

What do the Olympics have to do with computational complexity? Not much, so while I have spent much more time watching the games than proving theorems this week I couldn't think of the right way to fit it into the blog. Until I got the following email from David Pennock yesterday.

We implemented Olympics medal count prediction on Yoopick. Since it was your idea, you now have a moral obligation to blog about it, use it, and evangelize it to all your friends. :-)

Where most prediction markets track binary events, like whether the Obama will win the election, the Facebook-plugin Yoopick, developed at Yahoo Research in New York, is a fake-money market that predicts distributions over a range like the number of points scored in a basketball game. I suggested using Yoopick to predict the distribution of medals won by county and now you too can make your predictions and win some Yootles. I hear 100 Yootles and 2 Dollars will get you a subway ride in New York.

In other Prediction Market stuff at Yahoo, Sharad Goel used Amazon's Mechanical Turk to offer 100 people three cents each to predict the probability that Obama will win. The predictions were all over the place but average them up and you get exactly the same value as Intrade. Not the first time we've seen this phenomenon and it seems hard to explain.

And don't forget to check our our Electoral Markets Map. Obama has the slight edge as we get closer to the conventions and start of the real campaign season.

AI Follows Theory

In one of the 2006 AAAI Outstanding Paper Award Winners Model Counting: A New Strategy for Obtaining Good Bounds, Gomes, Sabharwal and Selman show how to approximately count the number of satisfying assignments of a Boolean formula with a SAT solver. They add random parity constraints ala Valiant-Vazirani and approximate the number of solutions based on the number of constraints needed until the formula is not satisfiable.

Sounds like a neat idea that complexity theorists should have come up with in the 80's. And we did, where by "we" I mean Larry Stockmeyer in his 1985 SICOMP paper On Approximation Algorithms for #P. Stockmeyer uses random hash functions from Sipser but it is essentially the same algorithm and analysis as Gomes et. al.

Stockmeyer wrote a purely theoretical paper. Since then we have better algorithms and much faster computers and one can now solve satisfiability on non-trivial input lengths. Gomes et. al. write the paper as a practical technique to approximate the number of solutions and even implement their algorithm and contrast with other programs that exactly count the number of solutions.

Gomes et. al. mention Toda's paper on the hardness of exact counting but don't cite Stockmeyer or any other paper in the vast theory literature on approximate counting.

We complexity theorists know many other nifty things one can do with an NP oracle such as uniform sampling and learning circuits. Read them now so you don't have to reinvent them later.

Ridiculously hard proof of easy theorem

Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently.

BILL: Justin, you've seen a proof of VDW's theorem, but there are easier things you haven't seen and should. Can you prove that the number of primes is infinite?

JUSTIN: Thats easy.

BILL: Good. How does it go?

JUSTIN: By the Green-Tao Theorem there are arbitrarily long arithmetic sequences of primes. Hence there are an infinite number of primes.

What to make of this?

1. Justin does not know how to proof the Green-Tao theorem (neither do I). However, if the proof does not use the fact that there are an infininte number of primes, then Justin's proof is valid. READERS: does anyone know, does it use the infinitude of the primes?
2. Justin now knows the standard proof. However, he should also learn that, at the level of math where he is at, you should be able to prove everything you use.
3. When does one start using theorems whose proofs one does not know? In research this is common. For basic coursework it should be rare.

Math Problems on vacation

SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We alternated.

1. I asked them: if there are n couples in a resturant, and everyone sits either across from or next to their darling at a rectangular table (nobody sits at the ends) then how many ways can they be seated?
2. They asked me: A marathon is 26.2 miles. A runner runs in such a way that during EVERY 1-mile interval he averages exactly 10 miles an hour. But his overall time is better than 10 miles an hour. How can this be?
3. I asked them: Show that if no matter how your 3-color the numbers {1,...,2006} there will be two points, a square apart, the same color.
4. They asked me: There is a bus where n people have assigned seats. The first person sits randomly instead of in his assigned seat. Henceforth, every person looks for his assigned seat, and if he does not find it, sits in a random seat. What is the prob that the last person sits in his assigned seat?

How did we do on these problems? They got my problems correctly. I basically got theirs (missed some points).

It was interesting coming up with problems that had not well known. I couldn't ask them truth-teller-and-liar problems or hats problems, since these are well known. Some of the problems above have appeared on this blog before. Not sure if that makes them well-known. At least they didn't know them. I tried asking the following problem that I thought was not so well known (I read it in American Math Monthly and told it to Peter Winkler two years ago-- he had not heard of it), but they had already heard it:

Here is a game: There are initially two piles of stones with a in one pile and b in the other. Every move a player removes a multiple of the smaller pile from the larger. If either pile has 0 in it then you cannot move. THe first player who can't move loses. For which (a,b) does player I have a winning stradegy.

Readers- I am not going to post solution. But you can in the comments!

What is the probability that ...

(I've been on vacation for the last 10 days on a Tauck Bus Tour of Canada with Heli-hiking.)

What is the probability that a bus tour has on it two people that know the proof that S2S is decidable? (Original Proof by Rabin is here. For reviews of several books on the topic see here.)

1. Not a trick question. The bus tour was not organized by the Association of Symbolic Logic.
2. The prob seems like it would be low. But this is not the right way to look at it.
3. This did happen. Suzanne Zeitman was on the tour. I learned about the proof from her (excellent) writeup which, alas, is not online. It is incorporated in the book The Classical Decision Problem by Borger, Gradel, Gurevich.
4. Should I be saying `WOW! that is so unlikely, yet it happend!'. No. Consider the following fictional conversation:
   
   BILL: The most amazing thing just happened! I just tossed a coin 40 times and got HHTTTHTHTHTHHTTTTHTHTHTTHTHHHTTHHTHTHHTH.
   
   LANCE: Why is that remarkable?
   
   BILL: Because the prob of that particular sequence is so small!
5. The prob that someone the distance away from me which Suzanne Zeitman is (I have written some math reviews for her and been in some email contact) happens to be on the same bus trip as me may be low, but its not so low as to be astonished if it happens. This is my third bus trip and the first time it happened. Is the probably 1/3? I doubt that, but its not so low as to be notable.
6. If before going on the trip I had said Gee, I wonder is someone who knows the proof that S2S is decidable will be on the tour? then THAT Would be notable.
7. What is the prob that the maintainer of the Erdos-Number Website was, Jerry Grossman, was on the trip? This is a trick question-- Jerry Grossman is Suzanne Zeitman's husband.
8. What is the prob that on the trip there were people who know, through their homeowners association, Steven Simpson an eminent logician who works on Reverse Mathematics, who I know. This did happen. Not a trick question, but again, not that notable.

Discounted Time

A write-up of some ideas I presented at the Complexity Conference Rump Session.


In computational complexity when we talk about time it usually represents a hard limit in the running time, solving the problem in time t(n). So we are happy, say, if we can solve the problem in one hour and miserable if it takes 61 minutes. But our real gradation of happiness over the running time is not so discontinuous.

Let's take an idea from how economists deal with time. They discount the utility by a factor of δ in each time step for some δ<1. What if we did the same for complexity?

Let δ = 1-ε for ε>0 and very small. Think ε about 10^-12. We then discount the value of the solution by a factor δ^t for t steps of computation.

Discounted time gives us a continuous loss due to time. It has the nice property that the future looks like the past: The discount for t steps now is the same as the the discount for the t steps already taken.

When t is small, δ^t is about 1-εt, a linear decrease. For t large, δ^t is about e^-εt, an exponential decrease.

We can also recover traditional complexity classes. DTIME(O(m(n)) is the set of languages such that for some constant c>0, δ^t>c for δ=(1-1/m(n)).

I'm not sure what to do with discounted time which is why this is a blog post instead of a FOCS paper.
Some ideas:

• What does average case and expected time mean in the discounted time model?
• What if you take the value of the solution of some approximation problem and discount it with the time taken? Can you determine the optimal point to stop?

The Gaza Fulbright Story

A story that has gotten far less press than it should have.

Seven Palestinians in Gaza received Fulbright grants this year. In May the US State department cancelled the grants because Israel closed the border between Gaza and Israel and the State department was afraid they couldn't get them out. After some noise got made, Condoleeza Rice stepped in and got the grants reinstated. Israel let in four of the seven so they could go to the American consulate to get visas but denied the other three for security concerns. For the other three, Rice got the state department to send a team and equipment into Gaza to help the remaining students who eventually got visas on July 30th.

Sounds like a happy ending. Alas that's not the end of the story.

A few days later, Fidaa Abed, one of the three, flew from Jordan to Washington and when he landed he learned that his visa was no longer valid. He was put back on a plane to Jordan. The other two hadn't left yet but their visas were also canceled. The decision to revoke the visas came after the US State Department received more information, probably from Israel.

More from the New York Times and the BBC.

A Theory of Reductions?

A guest post by Jens Zumbraegel

I am working on cryptography, and I came across complexity theory only recently. My question is whether a general framework for the various types of reduction exists. Let me give motivation:

The concept of reduction in order to compare the computational hardness of algorithmic problems is a very important one. However many types of reductions are used in the literature for different purposes. Trying a rough classification:

• "Classical" complexity theory: Karp/many-to-one or Cook reductions
• Average-case complexity: Karp reductions with a domination condition between distributional problems
• Cryptography: "reducibility arguments" in "provable security", i.e. ad-hoc reductions of the problem BREAKING-THE-CRYPTOSYSTEM to some well-known hard number theoretic problem, like FACTORING

I believe that a reduction theory for cryptographic purposes could simplify and structure many results in the area of provable security. Apparently there is not yet such a theory. One reason might be that although informally stated problems like "breaking the cryptosystem" have been formalized they do not fit into the framework of decision or search problems (they often involve oracle access for e.g. deciphering).

Back to my question - I wonder whether there is a general abstract theory of reductions, probably similar to category theory: One defines the class of algorithmic problems (the objects of the "category") and the type of reductions (the morphisms) one would like to consider. For example: (decision problems for languages in {0,1}^*, Karp reductions). Such a general framework could help to set up a reduction theory for cryptography.

Comments most welcome!

A Simple Heuristic

When I started off as a professor, my wife worked at a company called Teradyne, which makes testing equipment, as a master scheduler. A master scheduler makes the master schedule of what jobs get run on which machines at what time. As you readers already know, almost every interesting variation of job scheduling is NP-complete. As I was teaching intro theory at the time, I thought about bringing her in to give a lecture on how people deal with NP-complete problems in the real world.

So I asked my wife what algorithms she uses to make up the schedule. She had a simple rule:

Whomever yells the loudest gets their job scheduled first.

Needless to say I didn't bring her into class.

Analysis in Complexity

A shout out to my colleagues who have gathered in Banff for the BIRS workshop on Analytic Tools in Computational Complexity.

An important development in the study of computational complexity has been increased role of analytic methods. Fourier analysis has become an essential tool of the field, playing a critical role in the study of interactive proofs, the computational hardness of approximation problems, and the learnability of Boolean functions. The notion of Gowers uniformity (which was introduced by Gowers to give an analytic proof of Szemeredi's theorem on arithmetic progressions, and whose use can be viewed as "generalized Fourier analysis") has also been recently employed in the context of Probabilistically Checkable Proofs and hardness of approximation. A new paradigm in computational complexity is beginning to emerge, which involves reducing high dimensional discrete problems that arise in the study of Boolean functions to high dimensional continuous problems and then applying analytic methods to the resulting continuous problems.

I started graduate work in complexity right before the algebraic revolution that drove Razborov-Smolensky's circuit lower bounds, Toda's Theorem on the power of the permanent, the power of interactive and probabilistically checkable proofs and much more. But now, two decades later, algebraic techniques are producing diminishing returns and we have seen a growth in using real analysis in complexity as highlighted by this workshop. Avi Wigderson is giving a two-hour survey on "The Power of Partial Derivatives." Hard to have imagined a connection between partial derivatives and complexity.

What about those of us who went into computational complexity because we enjoyed discrete math? Should an old dog like me try to learn new tricks? Ah, the challenge of keeping up with a field that moves in mysterious new ways.

Complexity Special Issue

Here are the results of the vote taken after the special issue debate at the Complexity conference business meeting. The conference committee decided to stay with the Springer journal Computational Complexity for three more years and revisit the issue in 2011.

For those not invited to the special issue: I'd love to see your papers in ToCT but in any case please do submit to any of our community's fine journals. A conference proceedings should not be your paper's final resting place.