Movie Mistakes- or are they?

Note the following two movies mistakes. Or are they mistakes?

1. In The Wizard of Oz when the Scarecrow gets his diploma (instead of a brain) he says the following:

   The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side.

   This is incorrect. I suspect my readers spotted this mistake while watching the movie. If you type

   "Wizard of Oz" isosceles

   into google you get over 2500 hits-- far less than I would have thought. (Though if you replace isosceles with pythagorean you get over 8000 hits.) So this error is somewhat known. But is it an error? Possibilities:
   1. The writers and everyone who proofread the script did not catch this. Realize that this is not hard math. Wouldn't someone have noticed it?
   2. One of the points of the movie is that the Scarecrow is already smart. Hence the writers are trying to show that he was smart (though didn't know math) both before and after getting the diploma, so the diploma didn't change anything except his confidence. And when it comes to math, a misplaced confidence.
   3. Recall that the movie is all Dorothy's dream. The writers were making the point that Dorothy didn't know the proper way to state the theorem.
2. In Miracle on 34th street (1947 version) Kris Kringle, who claims to be Santa Claus, states that he has passed psychological tests, and brags that he knows that

   John Quincy Adams' vice president was Daniel Tompkins.

   But this is incorrect! John Quincy Adams's VP was John Calhoun! (Tompkins was James Monroe's VP.) How well known is this error? If you type

   "Miracle on 34th street" Tompkins

   into google you get over 1000 hits (far more than I would have thought). Is this really an error?
   1. Daniel Tompkins was our 6th VP. John Quincy Adams was our 6th Prez. They just didn't line up (see chart at the end of the answers to my prez quiz). Hence it was an honest mistake on the part of the writers (I find this far more believable than the Scarecrow-math error not being detected.)
   2. The writers were trying to tell us that Kris Kringle wasn't Santa Claus. Or at least put some doubt in our minds. Of course, that would only work if the audience knew their vice presidents. (Easy now with the excellent book Bland Ambition: From Adams to Quayle-- The Cranks, Criminals, Tax Cheats, and Golfers who made it to Vice President but harder in 1947 when the movie was made.
   3. There have been two remakes of the movie (that I know of) but I don't know if they contain the error. If you know, let me know.

A Great way to use a math blog

Timothy Gowers has suggested a line of research about the Density version of the Hales-Jewitt Theorem.. What is remarkable about what he proposes is that he wants a massive collaborative effort on it, as suggested in this blog entry of his. He has some other entries before that one ABOUT the notion of mass collaboration. Terry Tao has a companion post setting up a reading seminar on the density HJ theorem.

1. Both the collaboration and the reading seminar are great ways to use the Internet and their blogs! I often learn factoids or references from blogs. By contrast this gives people a chance to learn something deeper.
2. For LEARNING this is clearly a good idea that should work (if not for me then for others).
3. For PRODUCING new ideas I'll be curious how it goes. How productive does a research group get if it gets too big? At one point is there just too much noise? Then again, how many people are interested in this problem and this form of collaboration (I honestly do not know). Is not meeting face-to-face a problem?
4. Is this material important for TCS? Luca has a blog entry on the unreasonable effectivness of addive combinatorics in computer science, so that would be a YES.
5. Clearly I wish them well.

Sloan Fellows

The Sloan Foundation took out a full page ad in the New York Times today to announce the new Sloan Fellows. Many from our community on that page:

• Scott Aaronson
• Shuchi Chawla
• David Kempe
• James Lee
• Kamesh Munagala
• Ryan O'Donnell
• Luis von Ahn

Congratulations to all!

The Office

Suppose you had no specific reason to be on campus. No classes, no talks, no scheduled meetings with students/advisors, no meetings scheduled. Would you go to campus that day?

Not that long ago the answer would be of course you would. Maybe you might need to read a paper in a proceedings in your office or a journal in the library. You might have to have a short conversation with a colleague. You would need the computer (or secretary) at work to type up your paper.

Of course all of these activities can now be done electronically. Most of the time we spend at work gets spent on the same Internet we have access to at home or in the coffee shop. So why go to work?

We miss those random meetings. The people we bump into in the hallways. The tangents we have in lunch time discussions. Sometimes these meetings turn into important research projects or grant proposals. But more importantly they bring a sense of community. Often we get ourselves less attached to our departments, our colleagues and universities as we used to.

I'm not the first to say it, but as we get more connected we get more isolated. Technology will continue to push us in this direction: Who knows when we will all will take, if not teach, our courses on-line. Just remember you can't network if you are an isolated node.

STOC Papers

Last reminder: Complexity submission deadline tonight midnight Eastern.

In a nice move, Mitzenmacher posted both the titles and abstracts of STOC papers on the STOC website. Lots of strong papers, of course. Here are some that interest me for various selfish reasons.

• Exact Learning of Random DNF Formulas Under the Uniform Distribution by Linda Sellie. Linda was one of my first students at Chicago when I first started there in the late 80's but she had to leave graduate school early. But eventually she came back, kept working and received her Ph.D. from U. Chicago last spring under Stuart Kurtz with a thesis based on this nice learning result.
• An Axiomatic Approach to Algebrization by Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova. I like oracle results. I also like meta-oracle results. But especially I like meta-oracle results that generalize my meta-oracle results.
• A constructive proof of the Lovász Local Lemma by Robin Moser. The Lovász Local Lemma is a neat theorem that says if you have k events each occuring with probability p such that each event is independent of all but d other events than there is a positive probility that none of the events occur if ep(d+1)≤1 (no k in formula). Looks like Moser has a strong constructive proof. Alas while I like the Lemma, I never seem to have the right independence requirements whenever I want to use it.

Baseball Families and Math Families

(This article had help from Clyde Kruskal, Joe Kruskal, Bill Kahn, Hans Courant, and Lucy Moser.)

Bill James, the baseball statistician, once had an article on measuring Baseball Families. Who was the best baseball family? Would it be ...

1. The Alous: Felipe, Jesus, Matty were brothers. Moses was Felipe's son. All made the major leagues, and some of them were pretty good.
2. The Bonds: Bobby and Barry Bonds. Father/Son- both excellent. While you might rather have them then the four Alou's on your team, having four in a family just seems like a stronger family.
3. The Aarons: Hank and Tommie Aaron. Hank was a great player who hit 755 home runs (without steroids). Tommie, his brother, had a very short career. Even though its a real family, still doesn't seem like the right answer.
4. Babe Ruth alone: Bill James him rates as the best player of all time. Hence the "Ruth family" would seem to be a very good baseball family.

So, how to go about the question of who is the best baseball family ever? First we need a way to assign to a player some number saying how good he is. Bill James has already done this via a method called win shares. The idea is that you assign to a player how much he helped the team win. This is very complicated and I won't explain it here. However I will point out that it can't be negative and it varies quite a bit. For example Hank Aaron had 643 win shares, while his brother Tommie had 15. For some examples of players with high win shares see this.
So, you could just take the sum of the family members win shares. But this makes the family of one, the winner. We want a real family to get some credit for being a real family. Bill James' solution: Say the best person has a₁ win shares, the second a₂, etc. a₁ > a₂ > ... > a_n. Rate the family via a₁ + 2a₂ + ... + na_n. Under this metric the Alou brothers were the best baseball family as of 2003. See here for the numbers.

But I am still bothered. Why the combination a₁ + 2a₂ + ... + na_n? Is there some other way that is more mathematically sound or that can be derived? I doubt it since the question is somewhat subjective.

Clyde Kruskal has brought up another point. What if you had a longer link between relatives? What if you had a great-grandfather, grandfather, father, son. If the father is the best baseball player, start there. People who share half his genes (son and grandfather) count fully. But the great-grandfather counts less. You could even do this if someone in the family does not play baseball. We will see an example below under (what else) the Kruskal Math Family.

Who are the best Math families of all time? Here are some, not in order. I am sure there are more. Corrections and additions welcome! (I may make a website out of it.) I only count a family if it has at least three members and all of the people are related by blood (sorry Blums). Aside from that, I am fairly informal. This list is not meant to be the final word.

1. The Bernoulli Bunch Link. There were eight of them. Jakob-Bernoulli numbers, Nickolaus-Prob theory and Geometry (NOT Bernoulli Dist), Johann- Brachistochrone problem and possibly L'Hopital's rule, Daniel-Bernoulli's principal (also physics and probability), Wikipedia does not have info on the other four, but says they were math folks.
2. The Kruskal Kin: William (Kruskal-Wallace test in statistics), Martin (Solitons), and Joseph (Min Spanning tree, Kruskal Tree Theorem (set of all trees under embedding is a well quasi order), Kruskal-Katona Theorem). They are all brothers. Martin's son is Clyde (Parallel Computation, Coloring the Plane). Clyde's son is Justin (Ramsey Theory, though he's still in High School, so perhaps shouldn't count). William's son is Vincent (Computer Science-IBM research). Rosaly and Molly Kruskal are sisters of Martin/William/Joseph. They do not do math, but Molly has two sons who do math: William Kahn (statistician), and Ted Kahn (Statistical Software); and Rosalie's son is Jeremy Evnine (OR, Math Finance). (Using Clyde's theory these people would count some.) The following does not count as he is not a blood relative: Joe Kruskal's son-in-law is Neal Madras (Math prof at York Univ in Canada).
3. A Nest of Noethers: Father: Max Noether one of the finest mathematicians of the nineteenth century according to Auguste Dick who wrote a book on Emmy Noether. Max's son was Fritz Noether. Fritz Noether. Max's daughter was Emmy Noether the most important woman in the history of mathematics according to Einstein and others. (That was meant as a compliment but sounds so odd nowadays.) A great mathematician independent of her gender. The only father-son-daughter combination that I know of.
4. The Markov Chain: Andrey Markov (Markov Chains), his brother Vladmir Markov (Markov's inequality co-authored with his brother), and Andrey Markov Jr. (logic) son of Andrey Markov.
5. The Browder Brothers: Felix (PDE's), William (Topology and Geometry), and Andrew Browder (Analysis).
6. A Litter of Lenstras: Hendrik (Computational Number Theory), Arjen (Crypto), and Jan Karel.

Interesting misses:

1. A Research of Rabin's: Michael and Tal. A Father-Daughter both in Crypto. Probably the only such.
2. A Manifold of Millars: Terry and Jessica. A Father-Daughter both in Recursive Model Theory. Definitely the only such.
3. A Troop of Tardos': Eva and Gabor. The only other Brother-Sister combo I know of is the Noethers.
4. The Courant Clan: Richard Courant (Math), Hans Courant (son of Richard, Physics), Ernst Courant (son of Richard, Physics) Ted Courant (son of Hans, Math), Jurgen Moser (son-in-law of Richard, Math) Lucy Moser-Jauslin (Jurgen Moser's daughter, Math), Jerry Berkowitz (son-in-law of Richard, Math), Peter Lax (son-in-law of Richard, Math), Carl Runge (Father-in-law of Richard, Physics and Numerical Analysis). Note that Jurgen and Lucy Moser are a father-daughter combination.
5. A Band of Blums: Manuel and Lenore (married) and their son Avrim. All do TCS at CMU. Lenore-Avrim is the only mother-son combo I know.
6. A Geek of Gauss' or A Nerd of Newtons or An Egghead of Eulers or An Ark of Archimedes' are competitive with any of these families. But one person does not a family make.

Cleverness Squared

Many articles of interest in the New York Times.

Chris Maase pointed me to the article Scientists Disappointed by Direction of Financing.

Scientists, who were thrilled when President Obama vowed on his first day to "restore science to its proper place," have veered from excitement to dread as the stimulus bill makes its way through Congress.

I don't like the direction either, research funding down quite a bit from the original numbers in the stimulus plan. But I still expect science to get a nice boost from the stimulus. Did any of us guess back in December that the stimulus bill would have any science funding at all?

Steve Quake, a Stanford Bio-engineering professor, takes over as guest columnist on The Wild Side blog on the Times site. Quake's first column talks about the pressures of science funding.

I worry about the "opportunity cost" not only of the ideas not pursued and discoveries not made, but also of the time spent trying to convince very conservative review panels to fund one's research – each minute spent writing or administering grants is a minute that wasn't spent thinking deep thoughts about the frontiers of knowledge.

Could we stimulate more discovery and creativity if more scientists had the security of their own salary and a long-term commitment to a minimal level of research support? Would this encourage risk-taking and lead to an overall improvement in the quality of science?

I certainly have had my frustrations with the grant process and a few summers without salary in the past. Nevertheless the competition works well for us and we actually get more risk-taking to stand out from the pack.

Finally a new math puzzle, KenKen (Cleverness Squared), in the Times. So is the generalized n×n game NP-complete?

How Big is a Trillion?

Jason Hartline comments on a report by CNN about the size of the government bailout.

"To put a trillion dollars in context, if you spend a million dollars every day since Jesus was born, you still wouldn't have spent a trillion," McConnell said. CNN checked McConnell's numbers with noted Temple University math professor and author John Allen Paulos. "A million dollars a day for 2,000 years is only three-quarters of a trillion dollars. It's a big number no matter how you slice it," Paulos said.

Conclusion: At least one CNN reporter either doesn't know how long ago Jesus was born or cannot do basic arithmetic, so they found a mathematician who knows something about Jesus (John Allen Paulos is author of the book Irreligion: A Mathematician Explains Why the Arguments for God Just Don't Add Up) to ask for verification. Furthermore, the CNN editors found this to be reasonable investigative reporting. What!?!

Are results about actual constants interesting?

Josh Burdick had my course on concrete complexity a long time ago. He still dabbles in the area and recently sent me two manuscripts here and here

He seems to have proven the following:

PROBLEM: Given a 6 vertex graph (via (6 choose 2) Boolean inputs) you want to determine if it has a triangle. If you want to build a circuit for this problem just using NAND gates, how many are required.

PARTIAL ANSWER: The problem requires at least 21 NAND gates. ((6 choose 3), plus one output gate; what you'd probably expect, in other words.)

He has asked me two questions that I toss out to the audience

1. Is the result correct? (probably) Does it contradict anything known (I doubt that)? Does the proof seem correct? (I think so.)
2. Is the result interesting? To me this is the more interesting question (or meta-question). Are results about actual concrete numbers interesting? My first answer is only if (1) they lead to more more general results, or (2) use interesting techniques. So the answer may be, using (1), I DON"T KNOW, and (2) may be subjective.

The Ugly Proof

Alice: Does Carol's proof solve your big open problem?
Bob: Yes, but it's an ugly proof so it doesn't count.

A beautiful proof—a proof from "The Book"—is a piece of art. You take a look at it and just say "Wow!"

But what about the ugly proof. A boring case analysis that doesn't generalize and gives little to no insight as to why the theorem is true. A colleague, who for some reason wants to remain anonymous on this issue, has strong opinions about ugly proofs.

I guess the question is if there is a nicer proof or not. If there turns out to be, well and good. If not, probably it wasn't a very nice question. Nice questions have pretty answers.

I'm all for banning ugly proofs, except that there's likely to be a lack of agreement on what constitutes ugliness. The one positive aspect of an ugly proof is that it might lead to a nicer one. If not, it's worse than no proof at all.

I'm all for pretty proofs but if you have an open problem you care about, a need to get from point A to point B, while it is nicer to fly first class, getting to point B by driving a bumpy road still gets you to point B.

An ugly proof has the same logically correctness as a pretty one. Does the truth lack interest just because we had to take a painful path to get there?

New Blog on our blogroll: Be prepared to be blown away by BLOWN TO BITS

There is a new BLOG on our blogroll. It is Blown to Bits and it is associated to the book Blown to Bits: Your Life, Liberty, and Happiness after the digital Explostion by Hal Abelson, Ken Ledeem, and Harry Lewis.

1. The book is about how life has changed with the digital revolution. For more see my review either in an upcoming SIGACT NEWS or right here. Or better yet, buy the book.
2. The Blog will update the book. Note that there are events that happen in (say) 2009 that the book, published in 2008, would have wanted to cover, but couldn't. When we get time travel we can revisit this issue, and perhaps Abelso, Ledeem, Lewis will write a book on how that technology affects us. They won't need a blog to update the book.
3. The book Freakonomics has a blog associated to it. At first I didn't like the blog since I wanted it to be like the book. The book would take an observation or speculation and get real data on it and draw a conclusion. The blog would raise a question (Example: Why have paperboys on bicycles been replaced by papermen and paperwomen with cars?) and speculate (Example: it is more economically efficient) but not have any real information. This disapointed me since the books strength was to carefuly analyze. But now I like that blog since even raising issues is interesting (Example: I had not noticed that paperboys were being replaced by papermen and papewomen, but now I do.)
4. Similarly, the blog on BLOWN TO BITS cannot be as intellectually satisfying as the book. But it will be a good update on the book. And so far I have been very happy with it.
5. Disclosure: Harry Lewis was Bill Gasarch's advisor.

Stimulating Science

The stimulus package being shopped to congress by the Obama administration includes a considerable amount of science funding. The House passed a version that calls for an extra $2 billion dollars into core research at the NSF. The Senate is considering a bill that only gives an extra $1.2 billion for NSF core research. More details from AIP.

No doubt we need the additional funding. Scientific research has driven this nation's economy for many decades and we've let scientific research funding erode. The America Competes Act called for such funding but the full money has never been allocated. These funds, particulary the $2 billion, will put science funding back on track.

But does such increased science funding fulfill the main mission of the stimulus package, to get us out of the current recession and get people jobs now? Less clear.

Nevertheless the CRA is calling on us to contact our representatives in congress to push for the full science funding in the House stimulus bill. If we don't get science funding now, it will be very difficult to add it in the traditional budget process as the US faces a huge budget deficit.

While I was Gone

Just got back from vacationing in Obama's other home state and found a new govenor in Illinois when I got back. About time.

TTI-Chicago has moved into their new digs. Nice and spacious covering two floors soon to be connected by a bridge/stairway. And I get my own office for when I go down there.

Rocco Servedio is looking for a postdoc in learning/complexity at Columbia (email him if interested). Adam Klivans and David Zuckerman are looking for postdocs (plural) at UT-Austin. I've never seen a year with so many postdoc opportunities for complexity (and so few tenure-track jobs).

Paul Goldberg is looking for permanent faculty members (plural again) for a new Economics and Computation group in Liverpool. Economics is becoming the new quantum.

The Computational Complexity submission deadline is February 13, Electronic Commerce is February 9, ICALP is February 10th and many other conferences have deadlines very soon all vying for our just rejected STOC submissions. This list of papers that can't be submitted to another conference should, hopefully, appear here any moment now.

And you thought the STOC/FOCS deadline were pressure!

The James Bond Movie Goldeneye had the following scene which is typical of movies and some TV shows.

Scenario: A (good) female Russian computer programmer has made it really hard for the bad guys to do what they want to do. Boris is already working for the bad guys as a programmer.

BEGIN SCENE

HEAD BAD GUY: How long? (will it take to undo what she did)

BORIS: Two minutes... one minute.

HEAD BAD GUY: Guard! (he is calling over a guard who comes).

BORIS: I'm fixing it! (nervous)

HEAD BAD GUY: (to Guard) If he moves, kill him.

END SCENE

Boris was already on the bad guys side. Applying that kind of pressure seems counterproductive. Yet this is typical of bad guys in movies- they think that a threat of violence against a scientist already on their side will make them work faster- whether its programming or developing a nuclear bomb or whatever.

If the bad guy is trying to convince someone not on his side to work with him, then violence might make more sense. But even then, pressure may be counter productive. Better to offer the scientist a grant.

When to declare a problem is hard?/Constructive versions of Dilworth's theorem

Why do we think solving P vs NP is hard? There are some matematical reasons (oracles, Natural Proofs, Algebraization) but there is also this notion that many smart peoplet of people have worked on it.

If there is an open problem that not that many people have worked on, even if they are brilliant people, its hard to know how hard it is. I present an open problem of this nature.

Recall Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P).

Dilworths theorem is usually proven for the finite case and then, by the usual compactness arguments, holds for the infinite case. So the infinite case has a non-effective proof. The recursive math program tells us to ask the following questions.

1. Is there a computable function that will, given the Turing machine for a partial order on the set N (input (x,y), output 1 if x&le y, 2 if y &le x, 3 if x and y are incomparable) and given the width w, output a set of w total Turing machines that decide w disjoint chains that cover the partial order.
2. If not (and the answer is NO) then is there a weaker result that is effectively true?

Here is what is known (roughly):

1. For every w there is a computable partial order of width w that cannot be covered with ((w+1) choose 2)-1 recursive chains (it can be covered with ((w+1) choose 2) recursive chains). Proven by Szemeredi and Trotter but reported in Recursive Ordered Sets by Henry A. Kierstead, In the book Combinatorics and Ordered Sets. American Mathematical Society, 1986. The proof can also be found in my survey of recursive combinatorics.
2. There is an algorithm that will, given a computable partial order of width w, find a (5^w-1)/4 computable chains that cover it. (An effective version of {D}ilworth's Theorem by Henry A. Kierstead. Transactions of the American Math Society, vol 268, 63--77, 1981.)

The open problem is to CLOSE THAT GAP! How hard is this? I've asked around and it seems that while Hal Kierstead is a brilliant guy and he's had a few brilliant people have working on it, it remains uncracked. Does this mean its hard? Not necc. No matter how Brilliant the people working on it are, I think you need to have a community of people working on a problem for a number of years before you can say WOW, thats a hard problem!.

Random Thoughts on the Inaugural

RANDOM THOUGHTS on the inaugural. (After this post I will post on politics far less often.)

1. My colleague Evan Golub went into DC on Tuesday morning of the inaugural and photoblogged his day, much of which was spent on the National Mall awaiting and watching the swearing-in. Here it is: LINK
2. Most people who I know said they were not going since it was either to cold, to crowded, and they could get a better view on TV (I agree on all three counts). Some said that if they were 20 years younger they would go. But see next item.
3. The father of a friend of mine went! He is 78 years old! He told me before the inaugural: I didn't think I would see a black man inaugurated as President in my lifetime. I still won't believe it until it really happens. Thats why I want to be there! (He's also a democrat. I wonder what he would have thought if the first black president was a Republican.)
4. ***SORELLE*** went and blogged about it here.
5. I actually predicted it would be Obama vs McCain about 2 years ago. (I wish I had put it on record.) The reason: (1) Obama reminded me of Bill Clinton in that he was not known 4 years earlier and had a captivating style. (2) The Republicans tend to give it to someone that is already known, so McCain looked like a good bet.
6. Predictions for 2012. The Democrats will give the nomination to Obama easily (The last incumbent to not get the nomination was Lyndon Johnson, who didn't want it. Before that it was Chester A. Arthur who didn't want it. Before that it was Andrew Johnson. I don't know if he wanted it.) The Republicans will give it to someone we already know: either Romney or Palin. Perhaps the ticket will be Romney-Palin or Palin-Romney. Are Palin and Romney running? You betcha!
7. Ben and Jerry's is coming out with an Ice Cream to elebrate the Obama Inagural: Yes Pecan!

Prez Quiz ANSWERS and...

The ANSWERS to my Presidential Quiz are linked to here

First I'll answer the questions raised in the comments of the presidential quiz post.

1. Who served the most time as President and VP combined?
   
   Richard Nixon was VP for 8 years (Jan 1953-Jan 1961) and Prez for 5.5 years (Jan 1969-Aug 1974) for a total of 13.5 years. In second place is FDR who was Prez for 12 years 1.5 month (Mar 4, 1933-Apr 12, 1945) In third place is a tie between John Adams, Thomas Jefferson, and George Bush Sr. who all served for 12 years. (Adams and Bush did 8 years VP, 4 years Pres, while Jefferson did 4 years VP, 8 years Pres.)
2. Who was the last person before Bush Sr. who was elected President while holding the office of VP?
   
   Martin van Buren was sitting VP in 1836 and got elected. (He was Andrew Jackson's VP.)

There was one question (actually more) that were on the Prez Quiz originally but I removed. The reasons why they were removed point to some issues.

QUESTION: Who was the first female to run for president of the United States?

ANSWER: Historians say it was Victoria Chaflin Woodhull, Equal rights party, ran in 1872 and 1892. She did go around the country campaigning. This was before women could vote. Fredrick Douglas was her vice President. While historians acknowledge that she was the first female to run for president, under some stricter criteria her 1872 run does not count. Her name was not allowed to appear on any ballots and she got no votes. She died in 1927 and hence lived to see women get the vote and use it to elect Warren G. Harding. Oh well.

Under a stricter criteria the answer would be Belva Ann Lockwood who ran in 1884 and 1888. She was on some ballots and got 4100 votes. She died in 1917 and hence did not live to see women get the vote.

I removed the question because its ambigous. What does run mean? You can read a list of various people who may qualify at this website which has women who ran for president in any country.

History is full of ambigous questions. Discussing them is of interest. Seeing what prior generations thought of history may tell us about that generation. However, I prefer fields with definite answers.

Fooling Constant-Depth Circuits

Apparently Mark Braverman has settled a major open question about circuits due to Linial and Nisan. He shows that no poly-logarithmically independent distribution can be distinguished from a truly random distribution by a polynomial-size constant-depth circuit.

A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2^r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.

Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)^O(d2).

In a celebrated 2007 FOCS paper, Bazzi proved the result for the special case for DNF formulas (depth-2 circuits). Razborov recently had a simpler proof of Bazzi's theorem.

Nisan already created specific pseudorandom generators for constant-depth circuits but Braverman's result allows us to use any poly-logarithmically independent set including some that come out of coding theory. While the result doesn't have immediately obvious applications, I expect this result to be a fundamental tool for complexity for years to come.

Scott has a longer take and somehow manages to connect it with quantum computing.

Presidential Trivia Quiz !

Below is a Presidential Trivia Quiz. Some of the questions are obscure, so it might be more fun to just wait until Monday when I post the answers and then read the questions and answers together.

For those of you who like a challenge, you can take the quiz. There are several ways to do that (1) Take it without looking anything up on the web, or (2) Take it using the web and see how long it takes to finish it or (3) Use the web and score yourself on some combination of how many you get right and how long it took. Its 150 points so perhaps (SCORE) times (1/(NUM OF MINUTES)).

GRADING CRITERIA: Below there are 19 questions totaling 150 points. On the 5 points questions there is no partial credit. All of the 10 point questions ask for a list. If any one item on your answer is wrong then you get 0 points (so DO NOT GUESS!). If you get over half of the items, but not all of them then you get 5 points. If you get all of the items then, of course, you get 10 points.

POLITE REQUEST: Do not post any answers to these questions in the comments.

PERSONAL TRIVIA: This is the post I have spend the most time preparing by far!

1. (5 points) How many different people have or are been president?

2. (5 points) How many different people have been vice president?

3. (10 points) List all of the presidents that have died in office.

4. (10 points) List all of the presidents who have resigned.

5. (10 points) List all of the vice presidents that have died in office.

6. (10 points) List all of the vice presidents that have resigned.

7. (10 points) List all of the vice presidents that went on to be presidents.

8. (10 points) What is the max number of ex-presidents alive at the same time? List the times this has happened. Your answer should be a list of statements of the following form: Shortly after X took office there were Y ex-presidents: Z(1), Z(2), ... , Z(Y).

9. (10 points) What is the min number of ex-presidents alive at the same time? List all the times this has happened. Your answer should be a list of statements that (roughly) say During X's term there was a time when there were no living ex-presidents.

10. (10 points) List all of the presidents who got a patent.

11. (5 points) What is the most common first name for a president? List all of the presidents that had that name.

12. (10 points) List all of the presidents who lived at least 90 years (as of Jan 1, 2009).

13. (5 points) Who is the only deceased president who was not buried with honors? Why?

14. (10 points) List all of the presidents who later served in Congress or on the Supreme Court.

15. (10 points) List all of the presidents that ran again four or more years after leaving office.

16. (5 points) Name a fictional street gang named after a president.

17. (5 points) Who was the first president elected after women could vote?

18. (5 points) Who is the only person who was named after a president, and was played in a movie by an actor who later became president?

19. (5 points) In what movie did a main character get John Quincy Adams' vice president wrong?

Rightful Place

The state of our economy calls for action: bold and swift. And we will act not only to create new jobs but to lay a new foundation for growth.

We will build the roads and bridges, the electric grids and digital lines that feed our commerce and bind us together. We will restore science to its rightful place and wield technology's wonders to raise health care's quality and lower its costs. We will harness the sun and the winds and the soil to fuel our cars and run our factories. And we will transform our schools and colleges and universities to meet the demands of a new age.

All this we can do. All this we will do. – President Barack Obama, January 20, 2009.

The Dream

Less than two week after I was born, Martin Luther King, Jr. gave his "I Have a Dream" speech. Watch the speech if you haven't seen it yet. I consider it the greatest American speech captured on film.

Today in America we celebrate King's legacy. But King himself gets overshadowed by the realization of part of his dream as Barack Obama becomes the new leader of our nation. No post tomorrow in our recognition of the historic importance of tomorrow's events.

But King's vision has not been fulfilled in academia. We see very few African-Americans particularly in computer science. Why? Blacks certainly still face many more obstacles to succeed in academia. Those that succeed perhaps feel they can do more good as political or business leaders.

I appreciate the efforts of those, like my co-blogger Bill Gasarch, who make the effort to visit historically black colleges to talk to and recruit students or take part in the Richard Tapia Celebration of Diversity in Computing. But we have a long way to go.

King's dreams don't truly get fulfilled until we no longer have these discussions, when African-Americans can and do follow their paths in all aspects of society. Obama's inauguration is a big step, but full equality still, unfortunately, remains a dream.

Planes. Fellows. Power.

It was a common joke to point out how people really overestimate low or zero probability events. Why in the pre-flight briefing do the flight attendants teach us not one but two ways to inflate our life vests when there has never been a successful emergency water landing of a commercial airplane? Never. Ever. Until yesterday.

Suresh posts about the new ACM Fellows. Congrats to all!

Kirk Pruhs asks us to plug the Workshop on the Science of Power Management.

In particular it would be interesting to see if some interesting complexity theory could be built for energy/power as a resource instead of the usual complexity of space/time. On one hand, it is not immediately obvious how to do this as energy seems quite different than space/time, e.g. I guess there is no energy hierarchy theorem analogous to the space/time hierarchy theorems. On the other hand, I would be surprised if there is just no interesting complexity theory of energy.

In the Clinton administration it helped to make research relevant to the Internet. In the Bush administration it helped to make research relevant to national security. In the Obama administration it will help to make research relevant to energy and the environment. The beauty of complexity: It's always relevant.

Amitabh Varshney (Graphics Faculty at UMCP) emailing me the following:

Someone told me a while ago that there are some theory conferences in which members of the program committee are not allowed to submit papers. Is this really true? Does this still happen?

My first impulse was that theory conferences largely do not allow PC mems to submit (I knew that STOC, FOCS, COMPLEXITY did not, and that COLT did). By asking people (I could not find this info on websites) I have compiled the following list. Corrections and additions are welcome. PC stands for program committee.

1. Do not allow PC mems to submit: STOC, FOCS, ICALP, MFCS, COMPLEXITY, SODA, RANDOM, APPROX, SoCG
2. Up to the PC: LICS
3. Allow it but there are various restrictions: CRYPTO, EUROCRYPT, RECOMB (e.g., only two such submissions per person, or some complicated thing having to do with if students are co-authors. The exact rules change from year to year.)
4. Allow it with no restrictions: COLT, ALT, ISMB (biocomp), WABI (biocomp) EC (electronic Commerce)
5. My friends outside of theory tell me that allowing submissions from PC mems is the norm. Note above quote from Amitabh Varshney.

Now some RANDOM comments on this. I can submit the comments to RANDOM unless I'm on the PC.

1. Reason to allow it: if it is not allowed then people might decline to be on the PC.
2. Reason to not allow it: avoid conflict of interest and the appearance of conflict of interest.
3. For those that do allow it, the person who submitted is not allowed to be involved in the discussion. This works pretty well especially with meeting over-the-web.
4. From what I've seen and heard there is not a problem with the PC mems having an advantage. In fact, RECOMB explicitly says that a PC mems paper has to meet a higher standard. For other conferences this has been the de facto rule.
5. When COLT began the area of Learning Theory was small so they allowed PC mems to submit, else there would be too small a pool of people to submit. This is no longer true, but the rules live on.
6. The first few years of COMPLEXITY (then called STRUCTURES) the PC mems were allowed to give invited talks. This struck me as being a good way to reward the PC mems. But if they all want to do it, that is too many invited talks.
7. In COMPLEXITY this issue has not been revisited- it is not brought up at business meetings. According to Jeff Erickson's SODA BUSINESS MEETING BINGO it does come up at SODA business meetings. I've heard it also come up at SoCG business meetings.
8. If you let PC mems submit they you can have a large PC without depleting the pool of people who can submit.
9. I have no strong opinion on this issue. I'll leave that to the comments.

So You Think You Settled P verus NP

1. You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof.
2. You believe the proof is correct. Your belief is incorrect. Go back to step 1.
3. Are you making any assumptions or shortcuts, even seemingly small and obvious ones? Are you using words like "clearly", "obviously", "easy to see", "should", "must" or "probably"? You are claiming to settle perhaps the most important question in all of mathematics. You don't get to make assumptions. Go back to step 1.
4. Do you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time n^k (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
5. You submit your paper to an on-line archive. Maybe some people tell you what is missing or wrong in your paper. This should cause you to go to step 1. But instead you make a few meaningless changes to your paper and repost.
6. Eventually people ignore your paper. You wonder why you aren't getting fame and fortune.
7. You submit your paper to a journal.
8. The paper is rejected. If you are smart you would go back to step 1. But if you were smart you would never have gotten to step 7.
9. You complain to the editor that either the editor doesn't understand the proof or that it is easily fixed. You are shocked a respectable editor or journal would treat your paper this way.
10. You resubmit the paper, appeal, try other journals all to no avail.
11. You are convinced "the establishment" is purposely suppressing your paper because our field would get far less interesting if we settle the P versus NP problem so we have to keep it open at all costs.
12. If I tell you otherwise would you believe me?

Best Job?

Nicole Immorlica pointed me to a Wall Street Journal article about a ranking of 200 jobs by CareerCast. Number one: Mathematician.

So what is a mathematician? Does anyone actually get hired to be a mathematician as opposed to a professor, actuary, statistician or quant. The site defines mathematician as

Applies mathematical theories and formulas to teach or solve problems in a business, educational, or industrial climate.

But then why are jobs 2 and 3, actuary and statistician, listed as separate jobs.

Since the list does not contain computer scientist, mathematician is the closest to what I do. So I have the best job! Awesome. Thought I'd still rather be commissioner of Major League Baseball.

The Rating Methodology uses several categories: Work Environment, Physical Demands, Stress, Income and Outlook. The ratings lack a "fun factor" in any of these categories. Which sounds more fun: Actuary or Lumberjack (number 200 job)?

A Complete History of the LVDW conjecture

When you first make a conjecture you don't know if it will be important or interesting or both or neither. In the case below it was solved quickly, the answer was not interesting, and I doubt anymore will come of it. But, I did get a blog posting and some nice exercises for a class out of it.

Recall: VDW theorem is the following

For all k, for all c, for all c-colorings of N (the naturals) there exists a monochromatic arithmetic progression.

I was looking at a variant of this:

Definition: An arithmetic sequence is large if it is at least as long as its least element. The following are large arithmetic sequences: (1), (2, 10), (4,5,6,7). The following is NOT large arithmetic sequences: (100,102,104,...,118).

Note that for any c-coloring of N there is (trivially) a large monochromatic AP: just take (1). But what if we start coloring the naturals starting at k?

LVDW CONJECTURE: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a large monochromatic AP.

Why do I care? There is a Large Ramsey Theorem which is similar and is true. It is proven from the infinite Ramsey Theorem. It is of interest because this theorem is not provable in Peano Arithmetic (the associated functions grow faster than any function definable in PA). This leads to the following questions: I was hoping that LVDW CONJECTURE was true but ind of PA.

Alas, Andy Parrish (was Brilliant ugrad at UMCP in CS, is now brilliant grad at UCSD in math) proved LVDW CONJECTURE false. I leave it as an exercise.

There is a question that remains, though it just be equivalent to getting bounds on VDW numbers.

Definition: Let g:N &rarr N An arithmetic sequence is g-large if it is larger than g of its least element.

For which sequences of functions f_c is the following true: for all k, for all c, for all coloring c-colorings of (k,k+1,k+2,...) there exists a f_c-large monochromatic AP.

We know there is such a sequence by the ordinary VDW theorem (exercise).

Conferences Abroad

Samir Khuller guest posts about having conferences in exotic locations.

During the SODA Business Meeting I was a bit alarmed at some of the suggestions made for where the conference should be held in future years—some of the locations that even received substantial support were Paris and Buenos Aires. I have nothing against these locations, in fact Paris is one of my favorite cities to visit and Buenos Aires is high up on the places I want to visit. (I also want to visit Chile and Antarctica!) I wanted to make a few remarks about exotic locations.

1. The cost of sending students to conferences is already non-trivial. At least with NYC the travel costs are low for many students between DC and Boston. For faculty who are trying their best to stretch limited travel funds to pay for several students, moving the conferences to exotic locations makes life quite difficult. I would like to see major US conferences held in places where there is a substantial presence of students—Boston, Bay Area, NY, DC to name a few. We should move the conferences around, so that each student has an opportunity to attend a major conference in their area during their studies. If someone made a convincing argument about the benefit to Argentina theory grad students that would be an argument for Buenos Aires.
2. At a conference I spend 90% of my time indoors. For the 2 hours I spend outdoors each evening, it almost does not matter where one is. There are nice cities in the US to visit and NY, DC and San Francisco have emerged as popular locations, drawing a big audience. If we moved the conference or even alternated between the east and west coasts, that would be terrific.
3. There are visa issues for students on F1 visas making it tricky for them to attend meetings outside the US. For some students getting a visa involves them visiting their home country first, since they cannot get a re-entry visa to the US from some random country. There are already a lot of European theory conferences (SWAT, ICALP, ESA, STACS) to name a few. There are fewer conferences in N. America (STOC, FOCS, SODA). We had one STOC in Greece and one FOCS in Rome already. The other theory meetings such as PODC, PODS, LICS, SPAA already move around between Europe and N. America, why are we then taking our major conference and trying to move it to locations that make it harder for our students to attend?

Finally, if people suggested cities after checking prices at the major hotels that would be useful. While Paris has some reasonably priced small hotels, it could easily be that the large hotels are really expensive. We could then cast a more informed vote. The SIAM Disc. Math Conf. in contrast has extremely low registration fees and is usually held at a Univ campus during the summers.

Thanks to Moses Charikar and Sudipto Guha for comments.

Sorting a Partial Order

I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way.

What does it mean to sort a list? We usually think (correctly) that we take a list of ordered objects and put them into an ordered list. How to extend this to partial orders? We need to re-look at total orders.

Say that making a comparison between elements of the ordered set is HARD Then you want to make as few as possible. But you want to, when you are done, have a data structure that makes comparisons easy. Hence we view sorting as follows:

Given a set A of n elements from a totally ordered set come up with a data structure of size O(n) such that the operation Given x,y &isin A which one is bigger? can be done in O(1) time. While setting up the data structure you would like to to do this with as few comparisons as possible. We will assume that comparing two elements of {1,...,n} is easy.

Given a sorted array you can easily obtain such a data structure: pair each element with its index in the array. To compare x,y quickly just compare index(x) and index(y). Note that we think of comparing numbers in {1,...n} as easy but comparing elements of the ordered set as being hard.

The papers Sorting and Recognition problems for Ordered Sets (SICOMP 1988, Faigle and Turan) and Sorting and Selection in Posets (SODA 2009, Daskalakis, Karp, Mossel, Riesenfeld, Verbin) study this issue.

Definition: Let P=(X,<) be a partial order.

1. A chain decomposition of P is a partition of X into sets each one of which is totally ordered under < .
2. A chain merge data structure for P is a chain decomposition together with the following. For each x &isin X, the following information: (1) which i has x &isin C_i, and (2) for all j, what is the largest element in C_j that is < x. It is easy to see that from such a data structure you can do comparisons in O(1).
3. The width of P is the min number of elements in a chain decomp.

RESULTS:

1. Faigle and Turan showed that if P has width w then it can be sorted in O(wnlog n) comparisons. (Can also see Daskalakis et al paper for this.)
2. Daskalakis et al showed that if P has width w then it can be sorted in O(n(w+log n)). They use the Chain Merge Data Structure. This bound matches the info-theoretic min.

SODA and Me

There have been 23 IEEE Conferences on Computational Complexity and I have been to all of them. There have been 20 ACM-SIAM Symposiums on Discrete Algorithms and I have been to none of them. Yesterday Bill talked about the joys of SODA. So why haven't I gone?

I have nothing against SODA. The conference has strong papers and researchers. Algorithms is an important area of theory. But algorithmic results just don't excite me in the same way that a beautiful complexity result does. I don't mind a good algorithms talk every now or then but I don't think I could take three straight days of them.

When I applied for graduate schools my boss in Cornell Computer Services tried to talk me out of being a theorist. "Do you really want to spend your life shaving log factors off of running times?"

"Yes, I do," I replied. But in fact I don't and I didn't.

I have had two SODA submissions, both accepted to the 2003 conference in Baltimore. Right before SODA that year I was visiting Bill in College Park, south of Baltimore. As I drove back to New Jersey I pondered taking a right off the highway into the conference. But then common sense took over and I drove on.

I went to SODA 2009!

I just got back from SODA 2009 in New York (Symposium on Discrete Algorithms). In later posts I will describe some of the interesting papers that I saw, Today I'll just note some things.

1. Why did I go? One of the papers I covered in my grad class (On the Power of two, three, or four probes by Alon and Feige) was a SODA2009 paper, so I looked at the schedule and spotted 10 more papers that I was interested in. AND it was close AND my parents live in NY so no hotel fee AND school hasn't begun yet for me so no problem with missing appointments.
2. They had coffee but no food and no lunch. Since I recently was local organizer for COMPLEXITY (with Richard Chang and Marius Zimand) I KNOW how expensive food can be, so I have NO complaint here. I may never be able to complain about a conference again (unless its REALLY bad in which case I can complain more legit, or unless they claim to be refereed but are not).
3. They did not have proceedings! They had all of the papers on line at the SODA website, and they had a CD. PRO: no bulky proceedings to take home, might save paper. CON: Hard to browse through proceedings at conference or at home. This will get easier with technology. MY OPINION: Good Idea.
4. For me the talks were easier to understand than those at Complexity. This is because those that were on algorithms, describing the problem was reasonable (in complexity just describing the problem is hard) and those that were on complexity or combinatorics or some odd-ball mathematics, were the ones I was familiar with so could follow.
5. There were around 400 people there!
6. Was it worth going- YES. Will I go again- If the stars align themselves properly again then I will.
7. Michael Sipser once told me Its good to look at algorithms once in a while as a sanity check on your lower bounds.

Stephen Kleene: Not A Regular Guy

The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical computer science course more than Kleene. Kleene gave us

• Regular expressions and their equivalence to langugages accepted by finite automata. That's why we call them Regular Languages.
• Kleene Closure, the * operator in regular expressions. L^* is the set of all finite concatenations of strings in L. Source of great homework problems, for example: Show P is closed under Kleene closure.
• A recursive definition of Turing's languages, the reason they are often called Recursive Languages (though not without controversy).
• The terminology Church's thesis that we now call the Church-Turing thesis (though more controversy).
• The arithmetic hierarchy, a forerunner of our polynomial-time hierarchy.
• The S_mn theorem that one can uniformly hardwire part of the input into the code of a Turing machine.
• The recursion theorem (sometimes called the Kleene fixed point theorem) that informally says no matter how nasty the virus, some program remains unscathed.

and much more.

Klenne passed away January 25, 1994 in Madison, Wisconsin where he spent most of his academic career.

Randomness in Voting

Every voting scheme has the property that in some scenario a change of a single vote can change the outcome. When a major election has a very close result, like the current senate race in Minnesota or the 2000 presidential race in Florida, every vote gets scrutinized very carefully and the process can drag out for months.

This scrutinization ignores the randomness factor. Some people got stuck in traffic or maybe had some emergency that prevented them from voting. Some people went to the wrong voting area or their registration got lost. Some people just plain filled in the wrong oval, voting for the wrong candidate. These problems are rare and roughly cancel themselves out but in a very close election like Minnesota the randomness greatly outweighs the disputed ballots. Yet because of the hard cut-off the scrutinized ballots get the most attention.

I suggest we eliminate the hard-cut off by adding our own randomness. For simplicity suppose we had two candidates, Al and Norm, who received x and y votes respectively. We flip z=x+y uniform random coins. If the number of heads is at most x we declare Al the winner and Norm the winner otherwise. If x > z/2+ 10 z^1/2 then this process would make Al the winner almost all the time. But as x and y get very close the probability that Al wins approaches 1/2. Since a change of a few disputed votes won't affect the probability dramatically, we won't have so many battles over so little.

2008 Complexity Year in Review

Paper of the year goes to Optimal algorithms and inapproximability results for every CSP? by U. Washington grad student Prasad Raghavendra. The paper gives a semidefinite program approximating any constraint satisfaction problem, always the best possible approximation if the unique games conjecture holds.

Some other notables: Aaronson-Wigderson's Algebrization, Raz's counterexample to the strong parallel repetition theorem and many others. Another good year for Complexity.

Despite the dozens of "proofs" that have come my way, the P vs. NP problem remains open. Maybe next year.

NSF funding for theoretical computer science are at the highest levels since I started this blog. Princeton hosts a new NSF sponsored Center for Computational Intractability and Microsoft opened a new research lab in Cambridge, Mass. The theoretical computer science landscape looks quite strong.

However the current economic crisis will pose great challenges to computer science and all of academics as university budgets tighten. Great research can happen in awful economies—computability theory got its start during the great depression for example. But we all suffer if we lose a generation of theorists to this economy.

We remember David Gale, Nick Reingold, Ingo Wegener and others who inspired our lives, George Carlin, Arthur C. Clarke, Michael Crichton, Bobby Fischer and Randy Pausch.

We thank guest posters Richard Beigel, Manuel Bodirsky, Rance Cleavland, Iftah Gamzu, Evan Golub, Nicole Immorlica, Kamal Jain, Joe Kruskal, James Lee, Richard Matthew McCutchen, Amir Michail, Ketan Mulmuley, Vahan Mkrtchyan, Kirk Pruhs, Ken Regan, Rahul Santhanam, Uzi Vishkin, Philipp Woelfel and Jens Zumbraegel for their contributions to our blog this year.

A personal thanks to Bill Gasarch, not only for allowing me to come back to the blog and staying on as co-blogger, but also for organizing a great Computational Complexity Conference at Maryland.

I will always have many great memories for 2008. I started a new job at Northwestern in January and it was a great first year. My eldest daughter became a teenager and had her Bat Mitzvah in May. And after an entertaining election season, our junior senator is just weeks away from becoming the first African-American president of these United States of America. An exciting year indeed.

The Rooster

My daughters came up with the following joke.

Two roosters sat on on a barn. The first rooster asked the second what time he was supposed to crow. The second rooster replied "in the morning".

At 12:01 AM, the first rooster screamed "Cockle-Doodle-Do" waking up the farmer and his family. The second rooster said "Why are you doing that now?"

The first rooster said, "I looked up 'morning' in Wikipedia and it said morning starts at midnight."

The moral of the story: Don't trust Wikipedia.

After coming up with the joke, my daughters wanted to change the Wikipedia entry for morning to make the joke funnier but I talked them out of it. I always have a hard time convincing them that Wikipedia is usually quite trustworthy when their teachers at school keep pounding on how unreliable Wikipedia can be.

Enjoy the holidays. We'll be back next week with the Complexity Year in Review.

Springer Open Choice

First some administrative stuff. Posting will be light until the New Years. The comments feed is not working properly—Blogger is working on it. I deleted a spam comment from my spam post before I realized the comment was a joke. Sorry.

We just finished up an article for the Springer journal Theory of Computing Systems. If you go to the article's web page you'll see the paper is open access, you can download it from anywhere. How did that happen?

In the final stages of production, Springer offered us the opportunity to have our paper in their new Open Choice plan. For a fee we could have our paper downloadable with a license similar to that used by Creative Commons for non-commercial use.

That fee would be $3000, far too much than I'm willing to pay to let you download the paper from Springer when you can download a version from my home page for free.

But Springer has deals with some institutions, mostly Dutch, to offer Open Choice for all their papers. And one of my co-authors is Dutch. So enjoy!

No Good Deed Goes Unpunished

From the Ethicist in yesterday's New York Times Magazine.

Another college professor and I wanted a student to work on a project of ours, but she is a Mac user and the project required a program written for the PC. My colleague's husband, a Ph.D. in computer science, suggested an alternative program the student could download. She did; her computer froze and would not restart. The husband refused to assist her further. As the spouse of a colleague and the person whose advice caused the problem, isn't he obligated to help?

Randy Cohen, the Ethicist, gave a wishy-washy response that the husband doesn't have to help but he should.

Ignoring the whole Mac/PC issues, why is "a Ph.D. in computer science" relevant to the story? We don't get the fields of the questioner or the colleague.

I certainly would stop giving advice if every time I recommended a program there was an implicit promise of additional support. Though my Ph.D. is in Applied Math so the situation above doesn't apply to me.

Reminds me of some good advice I got as an undergrad when I was working as a programmer for Cornell computer services. Some person called me by mistake asking for some technical support and I helped him out. But then this person kept calling. My officemate suggested I give him some wrong but harmless advice. The caller thought I was an idiot and never called again. Problem solved.

Predicability in Movies: was there ever a case where...

This post was inspired by HALF of the movie FLIGHTPLAN.

I have watched HALF of the movie FLIGHTPLAN. In the movie Kyle Pratt (played by Jodie Foster- I didn't know that know that Kyle could be a girls name) takes her 6 years old kid on an airplane, the kid disapears, and the Flight Manifest said she was never there. So the captain and others think that Kyle is nuts.

Having not seen the rest of the movie yet I wonder which is true: (1) Kyle Foster IS nuts, or (2) there is some weird conspiracy going on. Gee, I wonder which one it will be!

In the real world I would of course assume (1). But since its a movie I absolutely know that (2) will be the case. The only point of suspense for me is will the final explanation make sense?.

SO, here is my question: Do you recall ever seeing a movie or TV show where it is clear that EITHER (1) the main character is nuts, or (2) there is a massive conspiracy. and it ends up being (1)? (I don't count if it ends up being a dream.)

YES, I know that if the main character was just nuts the story might not be as interesting. However, they should have the main character be nuts once in a while so that its not so predicable. That way when watching these things we would have a genuine question and genuine suspense. As for making it interesting- thats their job!

Have We Solved Spam?

The amount of spam in my spam folder has dropped below fifty per day down from several hundred a few months ago. The amount of spam that gets through Gmail's filters to my inbox is well under one a day. I'm not sure why. Better spam filters, better enforcement, less economic incentives for spam, maybe even the bad economy is playing a role. While not completely solved, email spam is no longer a significant problem for me.

This has happened without you having to pay me, solve a CAPTCHA or have your computer solve some hard problem to send me email. I have a mailto link on my home page (albeit generated by javascript code) and my various email addresses show up in plaintext on hundreds of pages scattered over the Internet.

For those of you who insist on making it painful to send you email (anything beyond a simple click or cut-and-paste without further editing), time to change your ways and not make your fear of spam make extra work for those of us who simply want to say hello, and maybe ask you to review a paper.

TEACH EVERYONE PROGRAMMING! (Guest Post)

(Guest Post by Amir Michail)

The case for teaching everyone programming

If everyone could program, then anyone could more easily and cheaply scale his/her world view to reach millions in one-on-one conversations to, for example, have greater impact on the results of an election.

If everyone could program, then anyone can more cheaply achieve immortality by encoding what they would like others to remember about them into a simulation of themselves.

Is it ethical to deny people such capabilities? Moreover, is it ethical to deny people the chance to dream up and create entirely new sorts of programs to enhance their lives?

But I hear you say that programming is a difficult skill that only a few could learn. Not really. Learning programming is easier than learning reading and writing, basic arithmetic, or playing a musical instrument. Programming at a professional level is hard, but so is writing a novel, proving theorems, or playing in an orchestra.

Nonetheless, we need to start thinking about ways to make programming more accessible to the vast majority of the population. This might mean taking the math out of programming and using languages that are not Turing-complete. Chatbot programming is one such example.

Prediction Markets Review

Yesterday the Electoral College delegates voted, 365 for Barack Obama and 173 for John McCain. How did the markets do?

To compare, here is my map the night before the election and the final results. The leaning category had Obama at 364. The markets leaned the wrong way for Missouri and Indiana, their 11 electoral votes canceling each other out. The extra vote for Obama came from a quirk in Nebraska that the Intrade markets didn't cover: Nebraska splits their votes based on congressional delegations, one of which went to Obama.

Indiana and Missouri were the most likely Republican and Democratic states to switch sides according to the markets, which mean the markets did very well this year again. Had every state leaned the right way (again), one would wonder if the probabilities in each state had any meaning beyond being above or below 50%.

Many argue the markets just followed the predictions based on polls like Nate Silver's fivethirtyeight.com. True to a point, Silver did amazingly well and the markets smartly trusted him. But the markets also did very well in 2004 without Silver. One can aggregate polls and other information using hours upon hours of analysis or one can just trust the markets to get essentially equally good results with little effort.

In some other prediction market news: A couple of years ago, Tradesports spun off their non-sports markets into a new site Intrade. Last month Tradesports shut down. Intrade still lives and hopefully it will continue to provide an exciting collection of political and other prediction markets.

Cantor Fitzgerald, owners of the Hollywood Stock Exchange, have filed with the CFTC to create real money markets based on box office receipts. Each share will pay off one-millionth of the first four weeks of the film's gross. They don't call it a prediction market since it doesn't have a binary outcome but I do because it is based on a specific time-limited event and the price should accurate reflect the expected gross of the movie.

Not market related but the big news in Illinois is of course the embarrassment of our governor right after the Obama high we've been on. At least Blagojevich will, hopefully, fade from view soon while Obama should leave a strong legacy as president that we in Illinois will remember for a long time.

A NIM-game and some possibly open problems

I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary difficulty.) It leads to other questions that may be open and/or interested. I state it differently then it appeared so I can more easily state the other questions.

Let A&sube N - {0}. Let n&isin N. NIM(A,n) is the following game: There are initially n stones on the table. Players I and II alternate removing stones from the table. They can remove x stones iff x &isin A. The first player who can't move loses. Let SQ be the set of squares. Show that there exists an infinite number of n such that Player II wins NIM(SQ,n).

1. Most people who read this blog should be able to do this problem. The solution is at the link above.
2. Let p &isin Z[x]. Let A_p = { p(x) : x &isin Z, p(x)>0 } It is easy to show that there are an infinite number of n such that player II wins NIM(A_p,n).
3. Let POW2 be the set of powers of 2. Let A=N-POW2. It is easy to show that there are only a finite number of n such that player II wins NIM(A,n).
4. OPEN: classify exactly which A are such that there are an infinite number of n such that Player II wins NIM(A,n). (Note- it may not have a nice classification.)

Request for Grant Reviewers from NSF

(Guest post from Richard Beigel, NSF Program Director for Algorithmic Foundations)

In order that proposals from CDI PIs (See below for what the CDI grants are) get a fair and knowledgeable review it is important that we have experts available for all areas covered by CISE to serve on these panels. To make this happen it is important to have the CISE community volunteer in large numbers to serve as reviewers for CDI. There is a webform available at here for anyone who wants to volunteer to review CDI proposals.

Cyber-Enabled Discovery and Innovation (CDI) is NSF's bold five-year initiative to create revolutionary science and engineering research outcomes made possible by innovations and advances in computational thinking. Computational thinking is defined comprehensively to encompass computational concepts, methods, models, algorithms, and tools. Applied in challenging science and engineering research and education contexts, computational thinking promises a profound impact on the Nation's ability to generate and apply new knowledge. Collectively, CDI research outcomes are expected to produce paradigm shifts in our understanding of a wide range of science and engineering phenomena and socio-technical innovations that create new wealth and enhance the national quality of life.

The Job Market

Bill's post Monday of a Michigan post-doc position garnished quite a few comments, generated by legitimate worries about the academic job market.

1992 was the single worst year so far in the CS faculty job market. Many of our students applied to 100-200 schools. Very few got good jobs and several others either left academics or took jobs at departments at levels well below their capabilities.

That bad job market discouraged many from getting Ph.D.s in computer science. But those who did graduated in the middle of the dot-com boom when CS jobs were relatively plentiful. The moral: Don't let today's job market determine whether you consider graduate school. By the time you finish your Ph.D. and a postdoc position, the recession should be well over and the first wave of theoretical computer scientists will start retiring.

That's little comfort for those searching for a faculty job this year. I expect this year's academic job market to be much worse than 1992, not just in theoretical computer science but in all academic disciplines. At Northwestern "hiring into new positions will be deferred as much as possible, while hiring into vacated positions will be carefully scrutinized to ensure that the prospective candidates present significant opportunities that might not be available in the future" and we are one of the healthiest financially. Harvard is freezing both hiring and faculty salaries. I'm hearing of many schools that plan to cut salaries.

Best suggestion is to ride it out. Take another postdoc or other temporary position. Consider jobs outside of North America. The disappearing slots will have to be filled once the economy rebounds and no one will hold it against you that you were unable to secure a US faculty job in 2009.

How was New York Theory Day?

REPORT AND REFLECT ON IBM/NYU/Columbia THEORY DAY

Most years in the FALL there is a THEORY DAY at NYU and in the SPRING there is a THEORY DAY at Columbia. They now call this IBM/NYU/Columbia Theory Day. The website did not say which numbered theory day, but the 2004 webpage for Theory day said it was the 25th one. If they have had these every semester since then... well, you can do the math.

1. I was GOING TO post about content of the talks. But the abstracts of the talks do a better job, so I refer you to those. Should I have stayed home and just read the abstracts? NO. Seeing someone give a talk on something does provide extra insight.
2. What does one get out of such things? It is good to know what is going on in theory, especially in parts of theory that you are NOT working on.
3. Why is it good? I could say you might switch areas OR you might spot a connection to your area and make a contribution OR you might get a paper out of it. While all of these are true, just KNOWING stuff is important. One tangible aspect of that is, if you are on a Program Committee you will have a better idea of the papers not in your area. Also, it helps you follow talks at the next theory day, or some other venue where their are talks not in your area.
4. I don't expect to follow that much of the talk. But I do expect (and this happened) to get introduced to an area and get some references that I may read later.
5. Talks are an hour long. If it's a relatively new field (e.g., on-line Ad slot scheduleing) this is good. If it's a survey talk (Joe Mitchell's talk was) this is good. If it's on a classical field that you are not familiar with and they are proving the very latest results, then a full hour is a bit much. But this is just from my viewpoint of wanting to be introduced to a field. wanting to be introduced to a field.
6. Most interesting thing I learned: Joe Mitchell, Comp Geom from SUNY Stonybrook, has had some of his work actually used by real people in the real world. (That may be a post later.) Since I am often skeptical of the practicality of theory, I was happy to hear this.
7. Oddest thing I learned: NYU and Brooklyn Poly-Tech are merging in some fashion. Nobody quite knows the details or what this means yet. I'm hoping it means that theory day will one day be at Brooklyn Poly-Tech which will make my train ride to theory day 15 minutes shorter.
8. New York Theory Day is usually announced about a month before it happens. This is not really enough time to plan. In fact, I have missed Columbia Theory day in the past because I had other plans by the time it was announced.

Ingo Wegener (1950-2008)

Philipp Woelfel remembers his advisor.

"Doktorvater" (doctor father) is the unofficial German term for PhD adviser – from my perspective, I can't think of a better word to describe my PhD adviser, Ingo Wegener, who passed away on November 26, 2008, after a long battle with cancer.

Probably many readers of this blog know about Ingo's work in complexity theory. Exemplary for his research are the topics of two of his monographs: The Complexity of Boolean Functions, 1987 (known to most of us simply as the Blue Book), and Branching Programs and Binary Decision Diagrams – Theory and Applications, 2000. Probably less known in this community is that about 10 years ago, Ingo began to investigate and analyze randomized search heuristics (evolutionary algorithms). Ingo and his research group strongly influenced the theory of this area; previously research was primarily experimental.

Ingo has been recognized as an outstanding scientist. He was a member of the "Wissenschaftsrat" (the most important scientific advisory committee of the German government), a member of the German Academy of Sciences Leopoldina, and the Academy of Sciences of Nordrhein-Westfalen. In 2006 he was awarded the Konrad-Zuse-Medal, the most prestigious German computer science award.

Here are some things I remember about Ingo (hopefully, some readers can add their recollections to the comments).

• Ingo always wrote his scientific texts by hand. And Ingo was an incredibly efficient writer: when he was writing his recent textbook Complexity Theory: Exploring the Limits of Efficient Algorithms, the students who were LaTeXing the manuscript, as well as those who were proof-reading it, used to complain that Ingo was preparing the manuscripts too fast for them to keep up. (Ingo was on Sabbatical, though.)
• Ingo was a gifted teacher. The students of the University Dortmund had an evaluation system, where each term they would elect the worst teacher, who would then be called "Lehrer Lempel" (sorry, probably only Germans understand the term). Ingo's lectures were known to be most difficult. Despite this, he usually came out "last" in the contest without any chance of ever winning the infamous "Lehrer Lempel" cup. In fact (according to Wikipedia) Ingo won the (real) teaching award of the University Dortmund twice.
• One of my favorite quotes is this. Asked about the difficulty of exams, he replied by asking whether anyone, who couldn't distinguish a kidney from a liver should be allowed to graduate from medical school...
• Ingo was one of the best organized people I have ever met. When I handed in my PhD thesis, Ingo said he'd be going to a workshop the next day, but he would write the report after returning. Sure enough, he came back from the workshop 5 days later, with the report on my thesis in his bag (and he wasn't a co-author of any of its papers).

We have lost an outstanding researcher, teacher, adviser, and friend, who for me was a true "Doktorvater".

A job posting for THEORY-Univ of Michigan

(Guest Post from Anna Gilbert from Univ of Michigan. Its actually a pointer to a job posting in theory!)

We have an opening for a postdoctoral fellow in Theoretical Computer Science at the University of Michigan. This is a joint position between the Department of Mathematics and the Department of Computer Science Engineering. Please apply by January 1, 2009 when we start reviewing applications.

Here is the URL for a more complete description. here

Science of Victory!

The Army has a new video The Science of Victory (via the CRA Blog).

An impressive argument for basic research though a bit heavy on the scare tactics.

Proofs Still Not Dead

Helger Lipmaa points to Justin Beldin's essay on the epistemology of Interactive/Zero-Knowledge proofs and asks my opinion on the general topic.

Reminds me of the 1993 Scientific American article "The Death of Proof" by John Horgan. Horgan talked about experimental proofs and computer-assisted proofs as well as interactive proofs. Most notably there was a sidebar story titled "A Splendid Anachronism?" on Wiles' then recent proof of Fermat's last theorem. It's nice to report that fifteen years later the traditional mathematical proof is not dead yet.

Back to Helger's question. I have no problems with the probabilistic aspect of interactive proofs. With a proper source of randomness, one can make the error so small it gets washed out by other cosmic effects. I have no problems with the interaction in an interactive proof either. I learn all proofs interacting, either with a person or a paper.

But a proof is something to be savored and shared and interactive proofs prevent both. One can understand a traditional mathematical proof at many levels of details, the same way one can read Shakespeare either as a quick read or looking at it in depth to find new meanings. Interactive proofs require proofs are the purely logical level, sort of like explaining the Mona Lisa by giving a bit map of the image. And in the end the verifier only gets to learn that there is a Mona Lisa, possibly without any idea what it looks like.

Moreover when you hear a great proof you want to tell the world, much the way you want to share a good joke, something I've occasionally done on this blog (proofs and a bad joke now and then). But an interactive proof of tautology or a zero-knowledge proof of satisfiability one cannot share. You believe but you cannot convince others.

Nothing against the theory of interactive proofs and zero-knowledge. What we can do with them is quite surprising, the applications, particularly to approximation algorithms and cryptography, are quite amazing and I'm lucky to have played a role in their development. But the proofs that interactive proofs do what they do will always excite me much more than the proofs they generate.

Quantum Leap/Quantum of Solace/What does Quantum mean anyway?

When the term quantum is used in English it often means large as in the TV show Quantum Leap. The recent James Bond Movie Quantum of Solace seems to use the word quantum to mean small (also the name of a bad guy organization). What should it mean to better reflect what it is in Physics?

1. Large: Quantum is discrete and hence moving in jumps is large compared to continuos things that move in very very small units (if units at all).
2. Small: The jumps are really small!
3. Neither: The point of Quantum is that things are discrete. This is neither large or small.

Some other random thoughts on this:

1. Was the term quantum originally a word in English that is now used for science, or was it originally a word in science that is now used in English?
2. The word random in English often means something slightly different- arbitrary.
3. The word continuos as it is used in math bothers me. There are some functions that look non-continuos but by the formal definition they are. The term uniformily continuos takes care of this, but they should just rename things so math-continuos matches common-sense-continuos.
4. Valiant defined a parsimonious reduction to be a reduction where the number of solutions is preserved (e.g., if SAT \le 3-COL via such a reduction f then if \phi has X sat assignments, then f(\phi) has X 3-colorings). I had never heard of the term parsimonious before I saw those reductions. It means thrifty but with a positive angle (as opposed to cheap). I don't quite see why thats really what you want to call these reductions.

How Many Sides to Your Error?

I often get asked various questions about complexity but I now had the same question asked twenty years apart.

Are there natural problems in BPP not known to be in RP∪co-RP?

Informally the class of BPP are the problems efficiently computable on a probabilistic computer with a very small chance of error. For RP if the program says "Yes" it is always right. For co-RP, if the program says "No" it is always right. The questions asks if there are any natural problems that have probabilistic algorithms that seem to require error on both the Yes and No answers.

In the late 80's, David Johnson asked me (and several others) the question when he was putting together his Catalog of Complexity Classes for the Handbook. I didn't have any examples and his catalog ended up citing the 1984 work of Bach, Miller and Shallit offering up Perfect Numbers (and some variants) an an answer to the question. But Bach et. al made their argument based on the fact that the current primality tests put Primes in co-RP but not in RP. In 1987, Adleman and Huang (building on Goldwasser and Kilian) put Primes in RP too. This puts Perfect Numbers in RP killing that example a few years before the Handbook appeared.

Since Primes were put in P in 2002, we have so few problems even known to be in BPP but not in P with the best remaining example the co-RP problem of determining whether two algebraic circuits are identical. So we still don't have any good answers to the above question except for some contrived problems like given three algebraic circuits, are exactly two of them identical. Most complexity theorists believe we have strong enough pseudorandom generators to avoid the randomness in probabilistic algorithms altogether. So in the end the question is likely irrelevant. Still we complexity theorists also like to know what we can prove beyond what we just believe.

All this doesn't mean BPP is not the right class to capture probabilistic algorithms when you can trust your randomness and don't mind a negligible error on either side. Complexity classes are defined to capture the properties we want them to have, not to mold to our limited knowledge of current problems.