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.