Interesting Math related to the Unexpected Hanging Paradox

In a prior post I pondered if there was interesting MATH that relates to the Unexpected Hanging Paradox. At the time none of the comments really had any and, alas, I thought there was not. (Thought looking back at the comments, the first one by Jeffe may be relevant.) But recently Ran Raz emailed me a pointer to this paper by Kritchman and Raz: The Surprise Examination Paradox and the Second Incompleteness Theorem. See also this post by Sam Alexander which explains some of the paper very well. The paper contains the following:

1. A new proof of Godel's incompleteness theorem that resembles the Surprise Exam Paradox. This is EXACTLY the kind of thing I was looking for.
2. An argument that suggests that Godel's incompleteness theorem can be used to resolve the paradox.

What does it mean to resolve a paradox? I resolve the unexpected hanging paradox by saying that the notion of Surprise is ill defined. The paper has a much more interesting viewpoint but that does not mean that it is correct. Which resolution is better the papers or mine? Not clear since it is unclear what it means to resolve a paradox. So what should YOU do? Read the paper and decide! Or just read it for the math.

What I Tweeted

Various thoughts not restricted to 140 characters.

Congrats to Mihalis Yannakakis for his election into the National Academy of Engineering as well as new Sloan Fellows Julia Chuzhoy, Rafael Pass, Chris Peikert, Mark Braverman and Anup Rao. TTI-Chicago gets no respect with TTI-C Prof Chuzhoy listed at University of Chicago but it should be fixed soon.

I called the Watson-Jeopardy match in 2009. The IBM segments during the show were great selling points for computer science. John Markoff wrote a nice wrap-up article for the Times but note the correction

An article last Thursday about the I.B.M. computer Watson misidentified the academic field vindicated by Watson’s besting of two human opponents on “Jeopardy!” It is artificial intelligence — not computer science, a broader field that includes artificial intelligence.

I skipped the various university viewing parties in favor of watching the shows with my daughter Molly. During current events in history class she went on a rant why everyone should think the Watson victory was "so cool". That's my girl.

Wolfram Alpha knows Computational Complexity. Pretty impressive but doesn't know everything. Jeff tweeted

When I ask "Is multiplication in AC0?" it tells me about the Ace of Clubs. Fail.

So we need Watson and Wolfram Alpha combined to make sense of our field.

Next week I'm off to Porto, home of Complexity 2012, for some Port Wine, a Francesinha and the thesis defense of co-author André Souto.

Aaron Sterling starts his own blog!

Aaron Sterling recently had an AWESOME guest post about Cheminformatics. That got such a great response that he has started his own blog Nanoexplanations. It shot to the TOP of our blogroll because we list thing alphabetically by first name. Kudos to Aaron's parents for seeing this day and naming him appropriately.

What will it be about? His guest post was on chemo-computing. More generally Aaron has been looking at nonstandard applications of theoretical computer science. That will be his topic.

A good blog should fill a need that is not being filled. His seems to be in that category--- I do not know of any blog covering non-standard applications. Not surprising- they are nonstandard! Is his goal to make these topics standard? At that point will he cease blogging? Only time will tell.

In the 2009 Year in Review post we noted that in 2009 we had annouced and added to our blogroll FIVE new blogs. In the 2010 Year in Review post we noted that in 2010 we had annouced and added to our blogroll NO new blogs. So blogging seemed to be in decline (granted this is a very small sample in a very small corner of the blogsphere). What is the trend? It is trendy to say that blogging is just so 2009 and that tweeting is the future, at least for the next 10 minutes. But to make predictions based on such little evidence is just so redonk.

Lincoln's Dog-Tail question (in honor of Presidents Day)

(Posted in Honor of Presidents Day.)

The following is NOT a trick question; however, I have heard two different answers for it.

How many legs would a dog have if we called the dog's tail a leg?

1. The answer is clearly 5- since 4+1=5. Duh.
2. Calling the tail a leg does not make it a leg. A dog has 4 legs. Duh.
3. I have seen people on either side not be able to even understand the other side's point.
4. This question has been attributed to Abraham Lincoln; however, just as Bogart never said Play it again Sam and Kirk never said Beam me up Scotty, Lincoln (likely) never said calling a tail a leg does not make it a leg (though he might have said Play it again Sam or Beam me up Scotty). See this interesting and serious post for information on what Lincoln said.
5. In our terminology Lincoln's point was that definitions should conform to reality and if they do not then it is the definitions that are wrong. I suspect he would not have liked the Banach-Tarski Pardox.

How would you answer the question? Do you understand the opposing viewpoint?

CCC 2011 papers- you heard it here first

The complexity papers for CCC 2011 are posted HERE. (They might not be at the official CCC site yet; however, I have permission to post here.)

1. Kudos to Omer Reingold- the notifications were sent out on TUESDAY, three days BEFORE the promised FRIDAY deadline.
2. Tuesday was also the ICALP deadline! I wonder if anyone took there CCC reject and submitted to ICALP. It would take rather fast turn around and they use diff formats.
3. I wondered why there was any delay between the notification to authors and the list being posted. Omer Reingold emailed me the following which explains it: ... it's important to make sure that authors provide updated information (updated title, list of authors affiliation) before posting
4. Some people have emailed be privately complaining that there is a bias towards complexity theory in CCC. I was at first skeptical (such talk was false for STOC 11), but after looking at the list of papers there seems to be some foundation to this concern. Of the 30 papers only 5 were on algorithms! If this conference is going to be that biased they should change the name from CCC to Conference on Computational Complexity.

If I tweeted here is what I would tweet

If I tweeted there is what I would tweet:

1. There was an interesting blog post that responded to Aaron Sterling's Chemoinformatics Post. See here for this interesting discussion.
2. See here for info on the Watson's performance on Jeopardy.
3. Why did Watson bet $937 on the Final Jeopardy question yesterday? (Tuesday) Zero would make sense. The max amount to guarantee victory even if he got it wrong would make sense. A nice round number to look more human would make sense.
4. The winner gets $1,000,000, second place gets $300,000, third gets $200,000. Ken Jennings and Brad Rutler have said they will give half of their winnings to charity. Watson said he would give all of his to charity. QUESTION: If you were on the show would you give 1/2 to charity? For Jennings and Rutler it isn't really hard to do since they already have lots of money from their prior Jeopardy appearances (though it is still admirable). But how about YOU?
5. Officially the authors of the CCC papers will be notified on Friday Feb 18. I have been told that this is an approx both ways. Could be earlier, could be later.
6. Some CCC notifications (all?) have been emailed. The list is not posted! At one time the quaint notion was that people should not find out if there paper got in or not by seeing someones telegraph message, website, or blog. Is this quaint-but-idiotic notion still in effect?
7. I got a copy of the complete Knuth Vol 4 in the mail today. How long have we been waiting for this? Knuth held a contest to name what we now call NP-completeness for use in this book.
8. Publishers have lists of people they send books to. As an editor for SIGACT NEWS I am on some of those lists. Today I got two copies of the exact same book. Both mailed to William Gasarch, SIGACT NEWS book review editor, Dept of CS, College Park MD, 20742. What was the book: Bijective Combinatorics.
9. CafePress.com emailed me a subject heading of gift of infinite choices. Alas, the actual letter said you can choose from 250 million styles and designs..
10. 12 days of Christmath (That is NOT misspelled.)
11. Also this one (I give two pointers in case one goes away.)

Can we Innovate without Producing?

On Friday I heard a speaker lament about how losing the manufacturing base in the US: "You can move a foundry easier than you can move an Internet company." An article in the New York Times has as its headline New York Times headline reads When Factories Vanish, So Can Innovators acknowledging the last metal flatware (think forks and spoons) plant to close in the United States.

On the other hand watch Austin Goolsbee explain Obama's National Wireless Initiative (via CCC blog).

Note the emphasis on job creation with almost exclusively service sector Internet jobs.

What's driven manufacturing overseas is not the Internet but the Box. Yet somehow we can continue to innovate,  with Microsoft, Google, Facebook, Twitter and Groupon all US made and continue to employ most of their workers in the US. Apple has had great hits with its physical devices like the iPhone and iPad but they are manufactured overseas. Even the next great fork design could easily come from the US even if those forks are made in China.

Our economy won't be won by keeping inefficient foundries in the US rather by improving on what we do best. As Obama puts it in the State of the Union.

Our free enterprise system is what drives innovation.  But because it’s not always profitable for companies to invest in basic research, throughout our history, our government has provided cutting-edge scientists and inventors with the support that they need.  That’s what planted the seeds for the Internet.  That’s what helped make possible things like computer chips and GPS.  Just think of all the good jobs -- from manufacturing to retail -- that have come from these breakthroughs.

Half a century ago, when the Soviets beat us into space with the launch of a satellite called Sputnik, we had no idea how we would beat them to the moon.  The science wasn’t even there yet.  NASA didn’t exist.  But after investing in better research and education, we didn’t just surpass the Soviets; we unleashed a wave of innovation that created new industries and millions of new jobs.

This is our generation’s Sputnik moment.  Two years ago, I said that we needed to reach a level of research and development we haven’t seen since the height of the Space Race... We’ll invest in biomedical research, information technology, and especially clean energy technology -- an investment that will strengthen our security, protect our planet, and create countless new jobs for our people.

Today Obama releases his budget for 2012 that should have dramatic cuts in many programs but growth for scientific research. It's going to be interesting.

PROS and CONS of being on a Program Committee

What are the PROS and CONS of being on a program committee?

1. PRO: Looks good on your resume. Is this true at your school? This PRO may be more relevant for untenured and un-full-prof people. (My spellcheck wanted me to use unturned instead of untenured.)
2. PRO: You get to see what people are working on. This may give you ideas of what to work on or of what papers to look at. You absolutely cannot use the ideas you see until they are in the public domain; however you can learn things and look up some past work.
3. PRO: If there is an in-person meeting then you get to meet some new people. (If there is NOT an in-person meeting then its not the same.)
4. PRO: You get to see how the process works which may help you when you submit later. Or it may help you decide not to submit.
5. CON: It takes a lot of time.
6. CON: You may have to read papers that you don't care about. (This could be good for you.)
7. CON: You may have to read bad papers. Not clear though- if you can tell its bad early on then you can skim the rest.
8. PRO AND CON: IF you also goto the conference then (a) you will understand more talks (b) you will be bored at more talks. I tend towards (a) but others tend towards (b).
9. PRO AND CON: You get to help decide what papers get in. But you may see things not go the way you think they should.

I'm sure there are more PROS, CONS, and THOUGHTS- please share them!

STOC 2011 accepte papers posted.You heard it here...12th!

For those who did not read yesterdays comments or Lance's Tweet (the empty set?) the list of accepted STOC papers is here.

1. 84 papers accepted. I personally think that there is enough high quality work that they should have more. However, I do not know what constraints the Program Committee had in terms of scheduling.
2. Lance thinks we should give up this model of high-prestige conferences all together and grow up. I am less radical--- I think that conferences should have higher acceptance rates and have other activities for people to get information out there. Posters, satellite workshops, rump sessions, and half-day seminars are all good. FCRC will have some plenary talks which is also good (I am not sure if they will have any of the other items I mentioned.) At a math conference I went to they had a Math Jeopardy competition for undergrads. That was JAWESOME!!! (My ugrads tell me this is the new `Awesome and it means Jaw-dropping Awesome. They could be punking me.)
3. Some people have said that there are less algorithms papers than usual or more complexity papers than usual (is that the same thing?). Is this a general trend for STOC and FOCS or is that just this one time?
4. Is it true? I tried doing a count but it was hard to tell how to classify things. Some papers were in both, some in neither, some hard to classify, The whole endeavor reminded me for the W(4,5)th time how pointless some classifications can be.
5. Is it important? If GREAT papers in algorithms do not get in because GOOD papers in complexity (or something else) do, that would be a problem. Other than that it is not a problem.
6. Lance has suggested that we should have a conference where all the subdisicplines of CS get together and hold hands and sing Kumbaya. Is FCRC like that? Is it as close as we'll ever come? Are there too many different subfields of CS that don't care about each other to really have a conference like that?

The Theory Postdoc Culture

FOCS Call for Papers posted. Deadline April 13.

The CRA organized a committee that put together on a white paper on whether postdocs are healthy for Computer Science. They are looking from thoughts and comments from the CS community that you can leave on that page. Suresh gave his thoughts last week.

Theoretical Computer Science, for better or worse, is ahead of this game. We have a plethora of postdoc positions available in our field. Combined with a relatively tight job faculty job market in the past few years, it is quite rare to see students in our community going immediately into a tenure-track job without a postdoc and a number of people are doing second and third postdocs. We haven't quite hit the point where it is impossible for a student to go right from Ph.D. to a tenure-track job at a major research university, but we are awfully close.

The computer science academic job market has ebbed and flowed since I was a graduate student. Most students believe the academic job market they see when entering graduate school will be similar when they get their Ph.D. Most students are wrong. Postdoc positions give some elasticity, filling in the gaps until the market moves back the other way.

When I got my Ph.D. I had a choice between a tenure-track at a good liberal arts college or a two-year assistant professor, basically a teaching postdoc, at the University of Chicago. I took the latter to keep my research career going and it did pay off for me--I had a good rookie year and the U of C kept me. It doesn't work as well for everyone but if postdocs can keep people's dreams alive that's a good thing.

All the news that fit to tweet

The Daily Shows Slogan used to be When news break we fix it! This raises the question: When does breaking news actually break?

1. (My memory of this may be hazy but something like it transpired.) In 1995 Bob Dole went on The David Letterman Show and said

   I will announce that I am running for president next week.

   David Letterman pointed out

   You just DID. NEWS ITEM: Bob Dole announces his candidacy on the David Letterman Show.

   I agree with Letterman- announcing that you are going to announce something is announcing it. I think Bob Dole got confused--- The David Letterman Show probably got more viewers than his press conference.
2. In this Jan 25, 2011 post Richard Lipton thanked me for my review of his book (and said some very nice things about me. THANKS!) Why Jan 25, 2011? Because this was shortly after the review appeared IN PRINT. However, in my Sept 9, 2010 post I had posted my review. Does appearing in print still have a certain Je ne sais quoi?
3. One of the many comments on Aaron Sterling's post on chemoinformatics was by Aaron Sterling himself. He wrote:

   It will be a while before this goes to press, so I can correct inaccuracies or address concerns before this becomes unchangeable.

   This is rather quaint. First off, goes to press? I think Aaron's guest blog will have more readers than my column. Aaron, your review is already out there. What does goes to press even mean anymore? Second off, what Aaron writes is not quite true. I keep all of the reviews online. If the review appears and 10 years later Aaron spots a typo and wants me to fix it on the online version, I would do it. For a big change I would make it a footnote and put a date on it. Page numbers are not a problem since the page numbers on my website copy are not the same as those in SIGACT NEWS anyway. And someone looking for the review would more likely find my website rather than there paper copy or the official ACM site (behind a paywall?) I will also keep the copy the Blog post points to up to date, so that is another free and easy-to-find place to find it.
4. A colleague was mentioned in The Online New York Times. The colleagues aunt wanted to know

   When will you be in the REAL New York Times.

   Is the aunt right? Does the REAL New York Times have a certain I-know-not-what that the online version lacks? The colleagues teenage son commented:

   Aside from far less people reading it, and getting ink on your hands when you do, what advantages does the so-called real NY times have?

   That may be an exaggeration (ink on your hands?) but he does have a point. See this for a counterpoint.